#!/bin/sh #| exec mzscheme -r "$0" "$@" |# (define names '()) ;; Thomas Baruchel (define (subsets l n) (let ((subsets* '())) (define (subsets0 l2 l* n2) (if (zero? n2) (set! subsets* (cons l* subsets*)) (do ((i 0 (+ i 1))) ((> i (- (length l2) n2)) subsets*) (subsets0 (list-tail l2 (+ i 1)) (cons (list-ref l2 i) l*) (- n2 1))))) (subsets0 l '() n))) (set! names (cons (list 's1 'subsets subsets) names)) ;; George Caswell (define (expand xs sets) (if (or (null? xs) (null? sets)) () (cons (apply append (map (lambda (set) (map (lambda (s) (cons (car xs) s)) set)) (cdr sets))) (expand (cdr xs) (cdr sets))))) (define (subs xs n) (cond ((eq? 0 n) ()) (else (do ((i 1 (+ i 1)) (acc (map (lambda (x) (list (list x))) xs) (expand xs acc))) ((= i n) (apply append acc)))))) (set! names (cons (list 's2 'subs subs) names)) ;; George Caswell (define (subs-base xs) (if (null? xs) () (let* ((rest (subs-base (cdr xs))) (first (if (null? rest) () (car rest)))) (cons (cons (list (car xs)) first) rest)))) (define (subs-expand xs sets) (if (or (null? xs) (null? sets) (null? (cdr sets))) () (let* ((rest (subs-expand (cdr xs) (cdr sets))) (first (if (null? rest) () (car rest)))) (cons (append (map (lambda (x) (cons (car xs) x)) (cadr sets)) first) rest)))) (define (subs2 xs n) (if (eq? 0 n) () (do ((i 1 (+ i 1)) (acc (subs-base xs) (subs-expand xs acc))) ((eqv? i n) (car acc))))) (set! names (cons (list 's3 'subs2 subs2) names)) ;; John David Stone (define (combos l n) (define (subsets0 l2 l* n2 acc) (if (zero? n2) (cons l* acc) (do ((rest l2 (cdr rest)) (available (length l2) (- available 1)) (acc acc (subsets0 (cdr rest) (cons (car rest) l*) (- n2 1) acc))) ((< available n2) acc)))) (subsets0 l '() n '())) (set! names (cons (list 's4 'combos combos) names)) ;; oleg@pobox.com (define (subset l n) (cond ((<= n 0) '(())) ((null? l) '()) ((= n 1) (map list l)) (else (append (let ((hd (car l))) (map (lambda (lst) (cons hd lst)) (subset (cdr l) (- n 1)))) (subset (cdr l) n))))) (set! names (cons (list 's5 'subset subset) names)) (define (memoize2 f) (let ((table (make-hash-table))) (lambda (x y) (let ((table2 (hash-table-get table x (lambda () (let ((t (make-hash-table))) (hash-table-put! table x t) t))))) (hash-table-get table2 y (lambda () (let ((r (f x y))) (hash-table-put! table2 y r) r))))))) ;; me (define (msubset l n) (cond ((<= n 0) '(())) ((null? l) '()) ((= n 1) (map list l)) (else (append (let ((hd (car l))) (map (lambda (lst) (cons hd lst)) (msubset (cdr l) (- n 1)))) (msubset (cdr l) n))))) (set! msubset (memoize2 msubset)) (set! names (cons (list 's6 'msubset msubset) names)) ;; me (define (msubset1 l n) (cond ((<= n 0) '(())) ((null? l) '()) (else (append (let ((hd (car l))) (map (lambda (lst) (cons hd lst)) (msubset1 (cdr l) (- n 1)))) (msubset1 (cdr l) n))))) (set! msubset1 (memoize2 msubset1)) (set! names (cons (list 's7 'msubset1 msubset1) names)) ;; ?? (define (subsets-v23 l n) (let loop ((l l) (ln (length l)) (n n) (prev-els '()) (accum '())) (cond ((<= n 0) (cons prev-els accum)) ((< ln n) accum) ((= ln n) (cons (append l prev-els) accum)) ((= ln (+ 1 n)) (let fold ((l l) (seen prev-els) (accum accum)) (if (null? l) accum (fold (cdr l) (cons (car l) seen) (cons (append (cdr l) seen) accum))))) ((= n 1) (let fold ((l l) (accum accum)) (if (null? l) accum (fold (cdr l) (cons (cons (car l) prev-els) accum))))) (else (loop (cdr l) (- ln 1) n prev-els ; new accum (loop (cdr l) (- ln 1) (- n 1) (cons (car l) prev-els) accum)))))) (set! names (cons (list 's8 'subsets-v23 subsets-v23) names)) ;; ?? (define (subsets-v5 l n) ; The initialization function. Check the boundary conditions (define (loop l ln n accum) (cond ((<= n 0) (cons '() accum)) ((< ln n) accum) ((= ln n) (cons l accum)) ((= n 1) (let fold ((l l) (accum accum)) (if (null? l) accum (fold (cdr l) (cons (cons (car l) '()) accum))))) (else (split l ln n accum)))) ; split l in two parts a and b so that (length b) is n ; Invariant: (equal? (append a b) l) ; ln is the length of l (define (split l ln n accum) (let loop ((a '()) (b l) (lna 0) (lnb ln)) (if (= lnb n) (cont a lna b lnb n accum) (loop (cons (car b) a) (cdr b) (+ 1 lna) (- lnb 1))))) ; The main body of the algorithm (define (cont a lna b lnb n accum) (let* ((accum (loop a lna n accum)) (accum ; this is actually (loop b lnb n accum) (cons b accum)) ) (let inner ((k 1) (accum accum)) (if (> k (min lna (- n 1))) ; don't loop past meaningful boundaries accum (let ((as (loop a lna k '())) (bs (loop b lnb (- n k) '()))) (inner (+ 1 k) ; compute the cross-product of as and bs ; and append it to accum (let fold ((bs bs) (accum accum)) (if (null? bs) accum (fold (cdr bs) (append (map (lambda (lst) (append lst (car bs))) as) accum)))))))))) (loop l (length l) n '())) (set! names (cons (list 's9 'subsets-v5 subsets-v5) names)) ;; ?? (define (stream-car s) (force (car s))) (define (stream-cdr s) (force (cdr s))) (define (stream-repeat x) (cons (delay x) (delay (stream-repeat x)))) (define (stream-ref s n) (if (= n 0) (stream-car s) (stream-ref (stream-cdr s) (- n 1)))) (define (stream-map f . streams) (if (null? (car streams)) '() (cons (delay (apply f (map stream-car streams))) (delay (apply stream-map (cons f (map stream-cdr streams))))))) (define (subsets-stream xs) (if (null? xs) (cons (delay (list '())) (delay (stream-repeat '()))) (let* ((r (subsets-stream (cdr xs))) (s (stream-map (lambda (ss) (map (lambda (y) (cons (car xs) y)) ss)) r))) (cons (delay (list '())) (delay (stream-map append s (stream-cdr r))))))) (define (ssubsets s n) (stream-ref (subsets-stream s) n)) (set! names (cons (list 's10 'ssubsets ssubsets) names)) (define (make-list n) (if (zero? n) '() (cons 'x (make-list (- n 1))))) (when (> (vector-length argv) 0) (let ((n (string->number (vector-ref argv 0))) (l (make-list (string->number (vector-ref argv 1)))) (f (assq (string->symbol (string-append "s" (vector-ref argv 2))) names))) (printf "~s/~s, ~s: " n (length l) (car f)) (time ((caddr f) l n)) (exit))) (define results (let ((r '( (=== testing 1 ===) (0 22 s1 0 0 0) (1 22 s1 0 1 0) (2 22 s1 0 2 0) (3 22 s1 10 13 0) (4 22 s1 70 69 0) (5 22 s1 380 385 100) (6 22 s1 1090 1092 280) (7 22 s1 2900 2897 880) (8 22 s1 6190 6161 2120) (9 22 s1 9480 9456 2680) (10 22 s1 14370 14337 4730) (11 22 s1 15860 15853 4430) (12 22 s1 17000 17004 5450) (13 22 s1 13530 13534 3690) (14 22 s1 9890 9883 2820) (15 22 s1 5750 5754 1500) (16 22 s1 2940 2931 800) (17 22 s1 1150 1148 270) (18 22 s1 360 360 60) (19 22 s1 100 90 10) (20 22 s1 20 15 0) (21 22 s1 10 2 0) (22 22 s1 0 0 0) (=== testing 2 ===) (0 22 s2 0 0 0) (1 22 s2 0 0 0) (2 22 s2 0 1 0) (3 22 s2 10 4 0) (4 22 s2 30 32 10) (5 22 s2 200 199 130) (6 22 s2 530 523 300) (7 22 s2 1920 1915 1350) (8 22 s2 4690 4672 3480) (9 22 s2 7060 7072 4910) (10 22 s2 11920 11915 8490) (11 22 s2 16430 16403 11630) (12 22 s2 19790 19732 13760) (13 22 s2 22310 22283 15390) (14 22 s2 22860 22825 15390) (15 22 s2 23080 23075 15390) (16 22 s2 23160 23160 15380) (17 22 s2 23230 23222 15380) (18 22 s2 23220 23213 15370) (19 22 s2 23200 23202 15340) (20 22 s2 23200 23199 15360) (21 22 s2 23210 23208 15340) (22 22 s2 23220 23213 15350) (=== testing 3 ===) (0 22 s3 0 0 0) (1 22 s3 0 0 0) (2 22 s3 0 0 0) (3 22 s3 0 2 0) (4 22 s3 40 39 30) (5 22 s3 150 154 100) (6 22 s3 650 654 450) (7 22 s3 1650 1629 1090) (8 22 s3 3180 3176 2010) (9 22 s3 6250 6221 4070) (10 22 s3 11020 10997 7620) (11 22 s3 13810 13801 9050) (12 22 s3 16360 16367 10440) (13 22 s3 18590 18568 11660) (14 22 s3 20450 20453 12870) (15 22 s3 20710 20711 12870) (16 22 s3 20910 20896 12910) (17 22 s3 20940 20931 12880) (18 22 s3 20900 20918 12860) (19 22 s3 20950 20965 12880) (20 22 s3 20960 20941 12900) (21 22 s3 20940 20964 12860) (22 22 s3 20950 20955 12870) (=== testing 4 ===) (0 22 s4 0 0 0) (1 22 s4 0 0 0) (2 22 s4 0 1 0) (3 22 s4 10 9 0) (4 22 s4 50 50 0) (5 22 s4 320 317 120) (6 22 s4 870 874 290) (7 22 s4 2360 2355 880) (8 22 s4 5150 5150 2150) (9 22 s4 7820 7802 2750) (10 22 s4 12070 12069 4860) (11 22 s4 13320 13298 4660) (12 22 s4 13300 13301 4540) (13 22 s4 11360 11360 3860) (14 22 s4 8330 8327 2890) (15 22 s4 4880 4883 1590) (16 22 s4 2480 2486 810) (17 22 s4 970 966 290) (18 22 s4 270 275 50) (19 22 s4 60 61 0) (20 22 s4 10 12 0) (21 22 s4 0 1 0) (22 22 s4 0 0 0) (=== testing 5 ===) (0 22 s5 0 0 0) (1 22 s5 0 0 0) (2 22 s5 0 1 0) (3 22 s5 0 6 0) (4 22 s5 70 77 30) (5 22 s5 510 509 280) (6 22 s5 2060 2059 1210) (7 22 s5 5630 5623 3210) (8 22 s5 13150 13152 7520) (9 22 s5 26120 26108 15430) (10 22 s5 41300 41275 24100) (11 22 s5 58040 58033 34130) (12 22 s5 63490 63415 34540) (13 22 s5 59720 59668 28110) (14 22 s5 52490 52440 20390) (15 22 s5 44080 43934 12480) (16 22 s5 38900 38857 8260) (17 22 s5 35550 35524 5560) (18 22 s5 33130 33173 3480) (19 22 s5 32280 32276 2850) (20 22 s5 31130 31084 1740) (21 22 s5 30540 30521 1150) (22 22 s5 30470 30484 1080) (=== testing 6 ===) (0 22 s6 0 1 0) (1 22 s6 0 0 0) (2 22 s6 10 1 0) (3 22 s6 0 3 0) (4 22 s6 30 26 20) (5 22 s6 130 138 90) (6 22 s6 490 489 350) (7 22 s6 1350 1333 980) (8 22 s6 2790 2775 2030) (9 22 s6 4550 4537 3290) (10 22 s6 6690 6670 4950) (11 22 s6 7360 7344 5280) (12 22 s6 7590 7576 5510) (13 22 s6 7670 7647 5860) (14 22 s6 5450 5443 4170) (15 22 s6 2850 2835 2090) (16 22 s6 1470 1459 1080) (17 22 s6 470 469 320) (18 22 s6 170 172 130) (19 22 s6 30 28 10) (20 22 s6 10 5 0) (21 22 s6 10 4 0) (22 22 s6 0 3 0) (=== testing 7 ===) (0 22 s7 0 0 0) (1 22 s7 0 0 0) (2 22 s7 0 1 0) (3 22 s7 10 4 0) (4 22 s7 20 26 10) (5 22 s7 150 139 110) (6 22 s7 490 488 340) (7 22 s7 1340 1339 970) (8 22 s7 2770 2757 2000) (9 22 s7 4550 4539 3310) (10 22 s7 7990 7997 6220) (11 22 s7 7360 7355 5300) (12 22 s7 8330 8331 6220) (13 22 s7 7660 7650 5870) (14 22 s7 5440 5436 4170) (15 22 s7 2820 2822 2070) (16 22 s7 1460 1456 1100) (17 22 s7 470 467 310) (18 22 s7 170 171 130) (19 22 s7 30 28 10) (20 22 s7 0 6 0) (21 22 s7 10 4 0) (22 22 s7 10 4 0) (=== testing 8 ===) (0 22 s8 0 0 0) (1 22 s8 0 0 0) (2 22 s8 0 0 0) (3 22 s8 10 7 0) (4 22 s8 40 35 0) (5 22 s8 210 204 60) (6 22 s8 670 667 240) (7 22 s8 1580 1568 550) (8 22 s8 3240 3249 1250) (9 22 s8 5310 5305 2040) (10 22 s8 7150 7148 2760) (11 22 s8 8640 8638 3800) (12 22 s8 7800 7797 3290) (13 22 s8 6790 6772 3300) (14 22 s8 3740 3738 1520) (15 22 s8 2360 2345 1160) (16 22 s8 1130 1126 620) (17 22 s8 390 385 210) (18 22 s8 100 99 50) (19 22 s8 10 9 0) (20 22 s8 10 2 0) (21 22 s8 0 0 0) (22 22 s8 0 0 0) (=== testing 9 ===) (0 22 s9 0 0 0) (1 22 s9 0 0 0) (2 22 s9 0 1 0) (3 22 s9 20 7 0) (4 22 s9 40 38 20) (5 22 s9 310 317 220) (6 22 s9 920 918 700) (7 22 s9 2430 2423 1860) (8 22 s9 3470 3468 2450) (9 22 s9 6770 6769 5130) (10 22 s9 10450 10431 8400) (11 22 s9 9390 9386 7140) (12 22 s9 10440 10442 8390) (13 22 s9 6760 6767 5160) (14 22 s9 5030 5026 4000) (15 22 s9 2480 2489 1860) (16 22 s9 980 985 660) (17 22 s9 470 469 300) (18 22 s9 150 152 80) (19 22 s9 50 44 10) (20 22 s9 0 10 0) (21 22 s9 0 2 0) (22 22 s9 0 0 0) (=== testing 10 ===) (0 22 s10 0 0 0) (1 22 s10 0 1 0) (2 22 s10 0 2 0) (3 22 s10 0 4 0) (4 22 s10 30 31 10) (5 22 s10 150 143 80) (6 22 s10 510 517 330) (7 22 s10 1280 1275 810) (8 22 s10 2970 2975 2060) (9 22 s10 5160 5151 3620) (10 22 s10 5980 5967 3840) (11 22 s10 8960 8957 6410) (12 22 s10 8880 8876 6330) (13 22 s10 7230 7226 5090) (14 22 s10 3860 3856 2330) (15 22 s10 2370 2373 1460) (16 22 s10 1390 1397 970) (17 22 s10 480 477 310) (18 22 s10 170 174 110) (19 22 s10 40 36 10) (20 22 s10 10 13 0) (21 22 s10 20 11 0) (22 22 s10 10 11 0) (=== testing 1 ===) (0 22 s1 0 0 0) (1 22 s1 0 0 0) (2 22 s1 0 2 0) (3 22 s1 20 14 0) (4 22 s1 70 70 0) (5 22 s1 390 384 110) (6 22 s1 1090 1090 250) (7 22 s1 2880 2875 860) (8 22 s1 6170 6159 2130) (9 22 s1 9450 9450 2670) (10 22 s1 14350 14331 4740) (11 22 s1 15850 15855 4450) (12 22 s1 16970 16971 5450) (13 22 s1 13510 13514 3670) (14 22 s1 9900 9888 2830) (15 22 s1 5760 5754 1510) (16 22 s1 2940 2936 800) (17 22 s1 1140 1146 270) (18 22 s1 360 361 60) (19 22 s1 90 90 10) (20 22 s1 20 16 0) (21 22 s1 0 2 0) (22 22 s1 0 0 0) (=== testing 2 ===) (0 22 s2 0 0 0) (1 22 s2 0 0 0) (2 22 s2 0 1 0) (3 22 s2 0 4 0) (4 22 s2 40 32 10) (5 22 s2 200 200 130) (6 22 s2 520 524 300) (7 22 s2 1920 1916 1390) (8 22 s2 4670 4666 3480) (9 22 s2 7060 7063 4890) (10 22 s2 11910 11909 8480) (11 22 s2 16420 16408 11590) (12 22 s2 19700 19711 13740) (13 22 s2 22280 22273 15350) (14 22 s2 22870 22843 15410) (15 22 s2 23090 23111 15350) (16 22 s2 23250 23230 15390) (17 22 s2 23300 23251 15420) (18 22 s2 23230 23233 15390) (19 22 s2 23210 23214 15360) (20 22 s2 23300 23259 15410) (21 22 s2 23240 23234 15360) (22 22 s2 23330 23258 15450) (=== testing 3 ===) (0 22 s3 0 0 0) (1 22 s3 0 0 0) (2 22 s3 0 1 0) (3 22 s3 0 3 0) (4 22 s3 40 39 30) (5 22 s3 150 155 100) (6 22 s3 650 653 450) (7 22 s3 1630 1629 1110) (8 22 s3 3190 3176 2030) (9 22 s3 6230 6221 4120) (10 22 s3 11000 11001 7630) (11 22 s3 13810 13803 9030) (12 22 s3 16450 16411 10470) (13 22 s3 18570 18565 11660) (14 22 s3 20400 20400 12880) (15 22 s3 20700 20706 12840) (16 22 s3 20920 20897 12930) (17 22 s3 20930 20928 12920) (18 22 s3 20900 20919 12900) (19 22 s3 20960 20959 12870) (20 22 s3 21050 20977 12910) (21 22 s3 21040 20962 12920) (22 22 s3 20970 20954 12940) (=== testing 4 ===) (0 22 s4 0 0 0) (1 22 s4 0 0 0) (2 22 s4 0 1 0) (3 22 s4 10 10 0) (4 22 s4 50 50 0) (5 22 s4 320 318 130) (6 22 s4 870 876 290) (7 22 s4 2350 2351 890) (8 22 s4 5140 5144 2140) (9 22 s4 7800 7801 2740) (10 22 s4 12070 12064 4850) (11 22 s4 13310 13299 4650) (12 22 s4 13300 13282 4520) (13 22 s4 11350 11349 3860) (14 22 s4 8330 8328 2910) (15 22 s4 4860 4857 1580) (16 22 s4 2500 2487 830) (17 22 s4 970 967 270) (18 22 s4 280 276 40) (19 22 s4 60 62 0) (20 22 s4 10 12 0) (21 22 s4 0 2 0) (22 22 s4 0 0 0) (=== testing 5 ===) (0 22 s5 0 0 0) (1 22 s5 0 0 0) (2 22 s5 0 0 0) (3 22 s5 10 7 0) (4 22 s5 80 76 40) (5 22 s5 510 509 270) (6 22 s5 2050 2054 1220) (7 22 s5 5620 5613 3160) (8 22 s5 13010 13015 7440) (9 22 s5 26020 26007 15380) (10 22 s5 41290 41252 24050) (11 22 s5 58010 57929 34130) (12 22 s5 63520 63450 34560) (13 22 s5 59730 59674 28060) (14 22 s5 52590 52565 20490) (15 22 s5 43910 43898 12480) (16 22 s5 38890 38855 8260) (17 22 s5 35550 35503 5530) (18 22 s5 33220 33184 3550) (19 22 s5 32330 32294 2830) (20 22 s5 31110 31052 1450) (21 22 s5 30500 30459 1130) (22 22 s5 30520 30499 1010) (=== testing 6 ===) (0 22 s6 0 0 0) (1 22 s6 0 0 0) (2 22 s6 0 1 0) (3 22 s6 0 3 0) (4 22 s6 20 26 10) (5 22 s6 140 138 100) (6 22 s6 490 488 340) (7 22 s6 1340 1331 960) (8 22 s6 2780 2774 2030) (9 22 s6 4540 4537 3270) (10 22 s6 6660 6660 4910) (11 22 s6 7360 7344 5290) (12 22 s6 7610 7581 5560) (13 22 s6 7670 7645 5890) (14 22 s6 5440 5434 4160) (15 22 s6 2830 2823 2080) (16 22 s6 1460 1456 1060) (17 22 s6 470 468 320) (18 22 s6 180 172 120) (19 22 s6 30 28 10) (20 22 s6 10 6 0) (21 22 s6 10 4 0) (22 22 s6 0 4 0) (=== testing 7 ===) (0 22 s7 0 0 0) (1 22 s7 0 1 0) (2 22 s7 0 1 0) (3 22 s7 0 3 0) (4 22 s7 30 26 10) (5 22 s7 140 138 100) (6 22 s7 490 487 330) (7 22 s7 1340 1332 970) (8 22 s7 2760 2752 2010) (9 22 s7 4540 4532 3320) (10 22 s7 8020 8006 6230) (11 22 s7 7360 7354 5300) (12 22 s7 8340 8340 6260) (13 22 s7 7650 7645 5830) (14 22 s7 5430 5438 4170) (15 22 s7 2840 2830 2090) (16 22 s7 1460 1455 1090) (17 22 s7 480 468 340) (18 22 s7 170 171 130) (19 22 s7 30 28 20) (20 22 s7 0 5 0) (21 22 s7 0 4 0) (22 22 s7 0 4 0) (=== testing 8 ===) (0 22 s8 0 0 0) (1 22 s8 0 1 0) (2 22 s8 0 1 0) (3 22 s8 10 6 0) (4 22 s8 30 34 0) (5 22 s8 200 204 60) (6 22 s8 670 668 230) (7 22 s8 1580 1570 540) (8 22 s8 3260 3253 1230) (9 22 s8 5310 5306 2030) (10 22 s8 7150 7156 2780) (11 22 s8 8650 8668 3760) (12 22 s8 7800 7797 3320) (13 22 s8 6770 6765 3280) (14 22 s8 3740 3735 1500) (15 22 s8 2340 2343 1160) (16 22 s8 1120 1123 640) (17 22 s8 400 386 230) (18 22 s8 100 100 50) (19 22 s8 10 10 0) (20 22 s8 0 1 0) (21 22 s8 0 0 0) (22 22 s8 0 0 0) (=== testing 9 ===) (0 22 s9 0 0 0) (1 22 s9 0 0 0) (2 22 s9 0 1 0) (3 22 s9 0 6 0) (4 22 s9 40 39 10) (5 22 s9 310 316 220) (6 22 s9 920 922 690) (7 22 s9 2440 2424 1870) (8 22 s9 3470 3467 2440) (9 22 s9 6790 6781 5140) (10 22 s9 10430 10423 8380) (11 22 s9 9420 9389 7180) (12 22 s9 10430 10432 8380) (13 22 s9 6770 6777 5170) (14 22 s9 5030 5028 4000) (15 22 s9 2480 2484 1870) (16 22 s9 990 983 660) (17 22 s9 470 469 300) (18 22 s9 160 152 80) (19 22 s9 40 44 10) (20 22 s9 10 10 0) (21 22 s9 10 1 0) (22 22 s9 0 0 0) (=== testing 10 ===) (0 22 s10 0 0 0) (1 22 s10 0 0 0) (2 22 s10 0 1 0) (3 22 s10 0 4 0) (4 22 s10 30 31 20) (5 22 s10 150 143 80) (6 22 s10 510 517 330) (7 22 s10 1270 1271 830) (8 22 s10 2990 2980 2080) (9 22 s10 5150 5148 3630) (10 22 s10 5990 5974 3850) (11 22 s10 9020 8993 6490) (12 22 s10 8880 8867 6350) (13 22 s10 7240 7233 5090) (14 22 s10 3850 3858 2380) (15 22 s10 2370 2374 1480) (16 22 s10 1410 1401 950) (17 22 s10 470 476 300) (18 22 s10 170 174 110) (19 22 s10 40 36 10) (20 22 s10 10 12 0) (21 22 s10 20 10 0) (22 22 s10 10 11 0) (=== testing 1 ===) (0 22 s1 0 0 0) (1 22 s1 0 0 0) (2 22 s1 10 2 0) (3 22 s1 10 13 0) (4 22 s1 70 69 0) (5 22 s1 390 383 120) (6 22 s1 1100 1093 260) (7 22 s1 2880 2881 870) (8 22 s1 6180 6161 2110) (9 22 s1 9490 9463 2680) (10 22 s1 14320 14327 4720) (11 22 s1 15940 15884 4460) (12 22 s1 16990 16985 5450) (13 22 s1 13510 13511 3700) (14 22 s1 9950 9910 2870) (15 22 s1 5760 5757 1520) (16 22 s1 2930 2935 800) (17 22 s1 1140 1145 260) (18 22 s1 360 362 70) (19 22 s1 90 89 10) (20 22 s1 10 16 0) (21 22 s1 0 2 0) (22 22 s1 0 0 0) (=== testing 2 ===) (0 22 s2 0 0 0) (1 22 s2 0 0 0) (2 22 s2 0 1 0) (3 22 s2 0 4 0) (4 22 s2 30 32 20) (5 22 s2 200 200 140) (6 22 s2 520 523 300) (7 22 s2 1920 1916 1360) (8 22 s2 4680 4676 3480) (9 22 s2 7070 7066 4860) (10 22 s2 11910 11910 8460) (11 22 s2 16410 16387 11610) (12 22 s2 19760 19721 13720) (13 22 s2 22280 22266 15370) (14 22 s2 22840 22827 15430) (15 22 s2 23170 23102 15410) (16 22 s2 23240 23204 15370) (17 22 s2 23230 23208 15340) (18 22 s2 23280 23262 15390) (19 22 s2 23390 23371 15450) (20 22 s2 23290 23278 15400) (21 22 s2 23280 23295 15420) (22 22 s2 23270 23296 15400) (=== testing 3 ===) (0 22 s3 0 0 0) (1 22 s3 0 0 0) (2 22 s3 0 1 0) (3 22 s3 0 3 0) (4 22 s3 40 39 30) (5 22 s3 160 155 110) (6 22 s3 650 655 470) (7 22 s3 1650 1636 1130) (8 22 s3 3170 3173 2040) (9 22 s3 6220 6239 4100) (10 22 s3 11040 11037 7610) (11 22 s3 13840 13850 9070) (12 22 s3 16400 16399 10400) (13 22 s3 18610 18601 11640) (14 22 s3 20410 20408 12880) (15 22 s3 20730 20732 12850) (16 22 s3 20860 20887 12840) (17 22 s3 20910 20893 12840) (18 22 s3 20990 20964 12920) (19 22 s3 20960 20966 12880) (20 22 s3 20950 20958 12870) (21 22 s3 21030 20987 12900) (22 22 s3 20950 20948 12870) (=== testing 4 ===) (0 22 s4 0 0 0) (1 22 s4 0 0 0) (2 22 s4 0 2 0) (3 22 s4 10 10 0) (4 22 s4 50 50 0) (5 22 s4 320 317 130) (6 22 s4 870 876 280) (7 22 s4 2350 2354 860) (8 22 s4 5150 5154 2140) (9 22 s4 7780 7808 2750) (10 22 s4 12050 12056 4840) (11 22 s4 13310 13300 4660) (12 22 s4 13330 13304 4550) (13 22 s4 11350 11356 3820) (14 22 s4 8320 8327 2910) (15 22 s4 4880 4873 1580) (16 22 s4 2490 2489 800) (17 22 s4 980 969 280) (18 22 s4 270 274 40) (19 22 s4 70 62 0) (20 22 s4 10 12 0) (21 22 s4 0 2 0) (22 22 s4 0 0 0) (=== testing 5 ===) (0 22 s5 0 0 0) (1 22 s5 0 0 0) (2 22 s5 10 1 0) (3 22 s5 10 7 0) (4 22 s5 70 76 20) (5 22 s5 510 508 280) (6 22 s5 2060 2059 1220) (7 22 s5 5640 5626 3170) (8 22 s5 13000 13007 7450) (9 22 s5 26060 26043 15340) (10 22 s5 41290 41297 24040) (11 22 s5 58000 58006 34130) (12 22 s5 63500 63471 34560) (13 22 s5 59810 59703 28080) (14 22 s5 52500 52478 20390) (15 22 s5 43920 43930 12480) (16 22 s5 38780 38784 8250) (17 22 s5 35460 35486 5510) (18 22 s5 33200 33211 3550) (19 22 s5 32330 32333 2760) (20 22 s5 31070 31103 1720) (21 22 s5 30540 30508 1170) (22 22 s5 30470 30471 1060) (=== testing 6 ===) (0 22 s6 0 0 0) (1 22 s6 0 0 0) (2 22 s6 0 1 0) (3 22 s6 10 3 0) (4 22 s6 20 26 10) (5 22 s6 140 138 100) (6 22 s6 490 491 350) (7 22 s6 1330 1331 960) (8 22 s6 2770 2767 2020) (9 22 s6 4550 4542 3330) (10 22 s6 6660 6658 4910) (11 22 s6 7380 7358 5290) (12 22 s6 7580 7572 5500) (13 22 s6 7640 7638 5850) (14 22 s6 5440 5434 4170) (15 22 s6 2830 2825 2090) (16 22 s6 1460 1456 1100) (17 22 s6 470 467 320) (18 22 s6 170 172 120) (19 22 s6 30 28 20) (20 22 s6 10 6 0) (21 22 s6 10 4 0) (22 22 s6 10 4 0) (=== testing 7 ===) (0 22 s7 0 0 0) (1 22 s7 0 1 0) (2 22 s7 0 1 0) (3 22 s7 0 3 0) (4 22 s7 30 26 10) (5 22 s7 140 137 100) (6 22 s7 490 487 330) (7 22 s7 1340 1338 980) (8 22 s7 2750 2750 2000) (9 22 s7 4560 4547 3310) (10 22 s7 8010 7998 6240) (11 22 s7 7350 7347 5280) (12 22 s7 8360 8360 6240) (13 22 s7 7670 7672 5870) (14 22 s7 5430 5443 4160) (15 22 s7 2820 2834 2080) (16 22 s7 1460 1457 1100) (17 22 s7 470 468 320) (18 22 s7 170 173 130) (19 22 s7 30 27 10) (20 22 s7 10 5 0) (21 22 s7 0 4 0) (22 22 s7 10 4 0) (=== testing 8 ===) (0 22 s8 0 0 0) (1 22 s8 0 0 0) (2 22 s8 0 1 0) (3 22 s8 10 6 0) (4 22 s8 30 34 0) (5 22 s8 200 205 70) (6 22 s8 670 670 240) (7 22 s8 1580 1570 560) (8 22 s8 3270 3259 1230) (9 22 s8 5310 5304 2050) (10 22 s8 7170 7149 2770) (11 22 s8 8640 8638 3800) (12 22 s8 7780 7783 3260) (13 22 s8 6770 6771 3280) (14 22 s8 3740 3740 1510) (15 22 s8 2330 2342 1160) (16 22 s8 1130 1123 620) (17 22 s8 390 384 220) (18 22 s8 100 100 50) (19 22 s8 10 9 0) (20 22 s8 0 2 0) (21 22 s8 0 0 0) (22 22 s8 0 0 0) (=== testing 9 ===) (0 22 s9 0 0 0) (1 22 s9 0 0 0) (2 22 s9 0 2 0) (3 22 s9 10 7 0) (4 22 s9 40 38 20) (5 22 s9 320 317 230) (6 22 s9 920 919 670) (7 22 s9 2420 2426 1870) (8 22 s9 3470 3462 2410) (9 22 s9 6750 6773 5140) (10 22 s9 10450 10440 8370) (11 22 s9 9400 9400 7150) (12 22 s9 10420 10440 8340) (13 22 s9 6760 6773 5150) (14 22 s9 5010 5025 3960) (15 22 s9 2490 2490 1870) (16 22 s9 980 986 650) (17 22 s9 470 471 300) (18 22 s9 150 152 80) (19 22 s9 50 43 10) (20 22 s9 10 10 0) (21 22 s9 0 2 0) (22 22 s9 0 0 0) (=== testing 10 ===) (0 22 s10 0 1 0) (1 22 s10 0 1 0) (2 22 s10 0 1 0) (3 22 s10 10 4 0) (4 22 s10 30 31 10) (5 22 s10 140 144 80) (6 22 s10 530 517 350) (7 22 s10 1280 1273 850) (8 22 s10 2990 2976 2050) (9 22 s10 5160 5155 3620) (10 22 s10 5990 5985 3830) (11 22 s10 8970 8971 6420) (12 22 s10 8880 8880 6330) (13 22 s10 7240 7230 5090) (14 22 s10 3870 3863 2360) (15 22 s10 2400 2401 1490) (16 22 s10 1390 1403 970) (17 22 s10 470 478 300) (18 22 s10 170 175 120) (19 22 s10 40 36 10) (20 22 s10 10 13 0) (21 22 s10 10 11 0) (22 22 s10 10 10 0) (=== testing 1 ===) (0 22 s1 0 0 0) (1 22 s1 0 0 0) (2 22 s1 10 2 0) (3 22 s1 20 14 0) (4 22 s1 70 69 0) (5 22 s1 390 386 130) (6 22 s1 1100 1094 270) (7 22 s1 2880 2883 880) (8 22 s1 6180 6170 2090) (9 22 s1 9500 9472 2690) (10 22 s1 14350 14341 4710) (11 22 s1 15900 15886 4460) (12 22 s1 17030 17023 5470) (13 22 s1 13590 13550 3690) (14 22 s1 9940 9910 2830) (15 22 s1 5770 5758 1490) (16 22 s1 2950 2936 790) (17 22 s1 1150 1149 250) (18 22 s1 350 359 70) (19 22 s1 90 89 10) (20 22 s1 10 16 0) (21 22 s1 0 2 0) (22 22 s1 0 1 0) (=== testing 2 ===) (0 22 s2 0 0 0) (1 22 s2 0 0 0) (2 22 s2 0 1 0) (3 22 s2 0 4 0) (4 22 s2 40 33 20) (5 22 s2 200 201 130) (6 22 s2 540 524 320) (7 22 s2 1910 1917 1360) (8 22 s2 4670 4669 3490) (9 22 s2 7090 7084 4910) (10 22 s2 11900 11903 8470) (11 22 s2 16430 16406 11640) (12 22 s2 19770 19734 13770) (13 22 s2 22320 22300 15400) (14 22 s2 22850 22838 15350) (15 22 s2 23110 23118 15390) (16 22 s2 23240 23204 15390) (17 22 s2 23320 23271 15440) (18 22 s2 23290 23262 15390) (19 22 s2 23260 23225 15400) (20 22 s2 23330 23254 15440) (21 22 s2 23290 23255 15390) (22 22 s2 23360 23283 15470) (=== testing 3 ===) (0 22 s3 0 0 0) (1 22 s3 0 0 0) (2 22 s3 0 0 0) (3 22 s3 10 3 0) (4 22 s3 40 39 20) (5 22 s3 150 153 100) (6 22 s3 650 654 460) (7 22 s3 1640 1629 1120) (8 22 s3 3190 3182 2060) (9 22 s3 6260 6226 4110) (10 22 s3 11040 11023 7650) (11 22 s3 13840 13835 9060) (12 22 s3 16470 16428 10430) (13 22 s3 18610 18588 11640) (14 22 s3 20420 20415 12870) (15 22 s3 20740 20752 12880) (16 22 s3 20950 20923 12920) (17 22 s3 20910 20915 12870) (18 22 s3 20930 20954 12850) (19 22 s3 20970 20973 12890) (20 22 s3 20980 20975 12910) (21 22 s3 21030 20983 12910) (22 22 s3 20950 20968 12870) (=== testing 4 ===) (0 22 s4 0 0 0) (1 22 s4 0 0 0) (2 22 s4 0 1 0) (3 22 s4 10 10 0) (4 22 s4 50 50 0) (5 22 s4 320 317 120) (6 22 s4 880 875 290) (7 22 s4 2360 2357 900) (8 22 s4 5150 5162 2150) (9 22 s4 7800 7802 2730) (10 22 s4 12090 12085 4850) (11 22 s4 13350 13327 4650) (12 22 s4 13300 13298 4540) (13 22 s4 11410 11366 3880) (14 22 s4 8340 8340 2890) (15 22 s4 4870 4874 1550) (16 22 s4 2510 2497 820) (17 22 s4 970 971 280) (18 22 s4 280 276 40) (19 22 s4 60 62 0) (20 22 s4 20 12 0) (21 22 s4 0 2 0) (22 22 s4 0 1 0) (=== testing 5 ===) (0 22 s5 0 0 0) (1 22 s5 0 0 0) (2 22 s5 0 0 0) (3 22 s5 10 7 0) (4 22 s5 70 79 30) (5 22 s5 500 515 280) (6 22 s5 2070 2063 1220) (7 22 s5 5640 5632 3180) (8 22 s5 13010 13026 7400) (9 22 s5 26050 26037 15330) (10 22 s5 41210 41218 24000) (11 22 s5 57900 57914 34060) (12 22 s5 63320 63342 34480) (13 22 s5 59640 59635 28040) (14 22 s5 52460 52436 20410) (15 22 s5 43920 43915 12480) (16 22 s5 38900 38902 8310) (17 22 s5 35490 35498 5530) (18 22 s5 33220 33165 3530) (19 22 s5 32360 32323 2810) (20 22 s5 31040 31043 1790) (21 22 s5 30520 30513 1090) (22 22 s5 30470 30471 1010) (=== testing 6 ===) (0 22 s6 0 0 0) (1 22 s6 0 0 0) (2 22 s6 0 0 0) (3 22 s6 0 3 0) (4 22 s6 20 26 10) (5 22 s6 140 138 80) (6 22 s6 480 488 340) (7 22 s6 1340 1334 960) (8 22 s6 2780 2770 2040) (9 22 s6 4540 4537 3310) (10 22 s6 6680 6667 4950) (11 22 s6 7350 7348 5270) (12 22 s6 7590 7572 5520) (13 22 s6 7650 7641 5880) (14 22 s6 5440 5432 4170) (15 22 s6 2830 2828 2090) (16 22 s6 1450 1454 1090) (17 22 s6 470 469 330) (18 22 s6 170 172 120) (19 22 s6 30 28 20) (20 22 s6 10 5 0) (21 22 s6 0 4 0) (22 22 s6 0 3 0) (=== testing 7 ===) (0 22 s7 0 0 0) (1 22 s7 0 0 0) (2 22 s7 0 1 0) (3 22 s7 10 3 0) (4 22 s7 30 26 20) (5 22 s7 130 138 90) (6 22 s7 490 488 340) (7 22 s7 1330 1336 950) (8 22 s7 2760 2752 2000) (9 22 s7 4560 4539 3300) (10 22 s7 8020 8014 6230) (11 22 s7 7340 7347 5300) (12 22 s7 8340 8335 6270) (13 22 s7 7640 7629 5840) (14 22 s7 5430 5438 4160) (15 22 s7 2820 2826 2070) (16 22 s7 1470 1458 1100) (17 22 s7 470 470 330) (18 22 s7 170 171 120) (19 22 s7 20 28 10) (20 22 s7 10 6 0) (21 22 s7 10 4 0) (22 22 s7 0 4 0) (=== testing 8 ===) (0 22 s8 0 0 0) (1 22 s8 0 0 0) (2 22 s8 0 1 0) (3 22 s8 0 6 0) (4 22 s8 40 35 0) (5 22 s8 200 204 70) (6 22 s8 670 667 230) (7 22 s8 1570 1570 550) (8 22 s8 3270 3262 1250) (9 22 s8 5310 5307 2050) (10 22 s8 7150 7156 2780) (11 22 s8 8660 8646 3780) (12 22 s8 7830 7810 3280) (13 22 s8 6770 6767 3280) (14 22 s8 3750 3739 1520) (15 22 s8 2350 2341 1160) (16 22 s8 1120 1126 640) (17 22 s8 390 384 200) (18 22 s8 100 100 60) (19 22 s8 10 9 0) (20 22 s8 10 1 0) (21 22 s8 0 0 0) (22 22 s8 0 0 0) (=== testing 9 ===) (0 22 s9 0 0 0) (1 22 s9 0 0 0) (2 22 s9 0 1 0) (3 22 s9 10 7 0) (4 22 s9 40 39 10) (5 22 s9 320 317 240) (6 22 s9 930 922 680) (7 22 s9 2420 2427 1850) (8 22 s9 3470 3462 2440) (9 22 s9 6770 6765 5160) (10 22 s9 10420 10423 8340) (11 22 s9 9420 9405 7150) (12 22 s9 10440 10427 8360) (13 22 s9 6770 6775 5160) (14 22 s9 5010 5023 3970) (15 22 s9 2490 2488 1880) (16 22 s9 980 984 650) (17 22 s9 470 469 330) (18 22 s9 150 152 70) (19 22 s9 40 44 10) (20 22 s9 10 10 0) (21 22 s9 0 1 0) (22 22 s9 0 0 0) (=== testing 10 ===) (0 22 s10 0 1 0) (1 22 s10 0 1 0) (2 22 s10 0 2 0) (3 22 s10 10 4 0) (4 22 s10 30 31 20) (5 22 s10 140 143 90) (6 22 s10 520 519 330) (7 22 s10 1280 1275 830) (8 22 s10 3000 2981 2090) (9 22 s10 5170 5168 3650) (10 22 s10 5970 5973 3840) (11 22 s10 9000 8993 6440) (12 22 s10 8920 8900 6370) (13 22 s10 7250 7242 5100) (14 22 s10 3860 3857 2330) (15 22 s10 2380 2375 1470) (16 22 s10 1410 1401 940) (17 22 s10 470 476 300) (18 22 s10 180 175 100) (19 22 s10 40 37 10) (20 22 s10 20 13 0) (21 22 s10 10 11 0) (22 22 s10 10 11 0) (=== testing 1 ===) (0 22 s1 0 0 0) (1 22 s1 0 0 0) (2 22 s1 0 2 0) (3 22 s1 20 14 0) (4 22 s1 70 69 0) (5 22 s1 380 384 120) (6 22 s1 1090 1091 280) (7 22 s1 2880 2880 870) (8 22 s1 6170 6160 2110) (9 22 s1 9470 9462 2670) (10 22 s1 14320 14330 4740) (11 22 s1 15840 15846 4440) (12 22 s1 17010 16995 5460) (13 22 s1 13540 13528 3710) (14 22 s1 9890 9897 2830) (15 22 s1 5740 5744 1480) (16 22 s1 2950 2934 790) (17 22 s1 1140 1145 260) (18 22 s1 360 360 70) (19 22 s1 90 89 10) (20 22 s1 20 16 0) (21 22 s1 0 2 0) (22 22 s1 0 0 0) (=== testing 2 ===) (0 22 s2 0 0 0) (1 22 s2 0 0 0) (2 22 s2 0 1 0) (3 22 s2 10 4 0) (4 22 s2 30 33 20) (5 22 s2 200 200 130) (6 22 s2 530 524 320) (7 22 s2 1920 1918 1380) (8 22 s2 4660 4670 3450) (9 22 s2 7070 7063 4870) (10 22 s2 11910 11907 8470) (11 22 s2 16370 16374 11590) (12 22 s2 19760 19736 13740) (13 22 s2 22270 22269 15360) (14 22 s2 22810 22803 15380) (15 22 s2 23090 23086 15380) (16 22 s2 23230 23202 15410) (17 22 s2 23210 23201 15340) (18 22 s2 23230 23220 15370) (19 22 s2 23260 23234 15360) (20 22 s2 23210 23210 15340) (21 22 s2 23220 23215 15390) (22 22 s2 23250 23227 15350) (=== testing 3 ===) (0 22 s3 0 0 0) (1 22 s3 0 0 0) (2 22 s3 0 0 0) (3 22 s3 0 2 0) (4 22 s3 30 39 20) (5 22 s3 160 154 90) (6 22 s3 660 654 460) (7 22 s3 1620 1624 1100) (8 22 s3 3180 3172 2020) (9 22 s3 6210 6210 4110) (10 22 s3 11020 11005 7620) (11 22 s3 13790 13802 9020) (12 22 s3 16390 16391 10400) (13 22 s3 18600 18574 11670) (14 22 s3 20430 20423 12890) (15 22 s3 20750 20733 12850) (16 22 s3 20900 20878 12940) (17 22 s3 20920 20917 12880) (18 22 s3 21000 20960 12900) (19 22 s3 20920 20915 12830) (20 22 s3 21040 20955 12930) (21 22 s3 20980 20939 12880) (22 22 s3 20980 20954 12890) (=== testing 4 ===) (0 22 s4 0 0 0) (1 22 s4 0 1 0) (2 22 s4 0 2 0) (3 22 s4 10 10 0) (4 22 s4 50 50 0) (5 22 s4 320 317 120) (6 22 s4 870 877 280) (7 22 s4 2360 2358 880) (8 22 s4 5160 5157 2150) (9 22 s4 7810 7807 2720) (10 22 s4 12090 12058 4820) (11 22 s4 13290 13284 4650) (12 22 s4 13290 13286 4540) (13 22 s4 11340 11343 3860) (14 22 s4 8330 8329 2890) (15 22 s4 4850 4850 1570) (16 22 s4 2490 2486 840) (17 22 s4 960 967 270) (18 22 s4 280 275 40) (19 22 s4 60 61 0) (20 22 s4 10 12 0) (21 22 s4 0 2 0) (22 22 s4 0 0 0) (=== testing 5 ===) (0 22 s5 0 0 0) (1 22 s5 10 0 0) (2 22 s5 0 1 0) (3 22 s5 10 7 0) (4 22 s5 70 77 30) (5 22 s5 510 508 260) (6 22 s5 2050 2054 1200) (7 22 s5 5610 5611 3170) (8 22 s5 13020 13017 7480) (9 22 s5 26100 26077 15370) (10 22 s5 41350 41301 24120) (11 22 s5 58370 58498 34410) (12 22 s5 63640 63597 34610) (13 22 s5 59690 59675 28070) (14 22 s5 52660 52615 20570) (15 22 s5 43940 43917 12440) (16 22 s5 38790 38780 8210) (17 22 s5 35510 35501 5490) (18 22 s5 33240 33192 3540) (19 22 s5 32330 32325 2810) (20 22 s5 31080 31063 1780) (21 22 s5 30570 30514 1170) (22 22 s5 30500 30499 1080) (=== testing 6 ===) (0 22 s6 0 0 0) (1 22 s6 0 0 0) (2 22 s6 0 1 0) (3 22 s6 0 2 0) (4 22 s6 20 26 10) (5 22 s6 140 138 100) (6 22 s6 490 488 330) (7 22 s6 1330 1332 950) (8 22 s6 2770 2769 2030) (9 22 s6 4550 4537 3260) (10 22 s6 6660 6666 4930) (11 22 s6 7370 7359 5320) (12 22 s6 7590 7572 5500) (13 22 s6 7670 7641 5880) (14 22 s6 5460 5432 4180) (15 22 s6 2820 2825 2060) (16 22 s6 1450 1457 1080) (17 22 s6 470 471 320) (18 22 s6 170 172 120) (19 22 s6 20 28 10) (20 22 s6 10 6 0) (21 22 s6 10 4 0) (22 22 s6 0 4 0) (=== testing 7 ===) (0 22 s7 0 0 0) (1 22 s7 0 0 0) (2 22 s7 0 1 0) (3 22 s7 0 3 0) (4 22 s7 30 26 10) (5 22 s7 140 138 90) (6 22 s7 490 489 350) (7 22 s7 1330 1333 970) (8 22 s7 2770 2759 2010) (9 22 s7 4540 4541 3280) (10 22 s7 8010 8001 6210) (11 22 s7 7340 7342 5270) (12 22 s7 8340 8325 6260) (13 22 s7 7650 7631 5870) (14 22 s7 5450 5439 4190) (15 22 s7 2840 2826 2060) (16 22 s7 1450 1456 1070) (17 22 s7 470 467 330) (18 22 s7 170 172 130) (19 22 s7 30 27 10) (20 22 s7 0 6 0) (21 22 s7 10 4 0) (22 22 s7 0 4 0) (=== testing 8 ===) (0 22 s8 0 0 0) (1 22 s8 0 0 0) (2 22 s8 0 1 0) (3 22 s8 10 6 0) (4 22 s8 40 35 0) (5 22 s8 210 204 70) (6 22 s8 670 672 250) (7 22 s8 1570 1567 540) (8 22 s8 3250 3253 1220) (9 22 s8 5290 5293 2050) (10 22 s8 7130 7136 2770) (11 22 s8 8660 8641 3780) (12 22 s8 7790 7783 3270) (13 22 s8 6780 6767 3260) (14 22 s8 3730 3733 1520) (15 22 s8 2360 2344 1170) (16 22 s8 1130 1126 640) (17 22 s8 390 384 210) (18 22 s8 100 100 60) (19 22 s8 0 9 0) (20 22 s8 10 2 0) (21 22 s8 0 0 0) (22 22 s8 0 0 0) (=== testing 9 ===) (0 22 s9 0 0 0) (1 22 s9 0 0 0) (2 22 s9 0 2 0) (3 22 s9 10 7 0) (4 22 s9 50 39 10) (5 22 s9 310 316 230) (6 22 s9 930 920 690) (7 22 s9 2440 2424 1870) (8 22 s9 3470 3461 2440) (9 22 s9 6030 6020 4420) (10 22 s9 10420 10425 8350) (11 22 s9 9400 9388 7140) (12 22 s9 10430 10426 8350) (13 22 s9 6790 6776 5190) (14 22 s9 5040 5025 3970) (15 22 s9 2480 2484 1860) (16 22 s9 990 987 650) (17 22 s9 480 470 300) (18 22 s9 150 152 60) (19 22 s9 50 43 10) (20 22 s9 10 10 0) (21 22 s9 0 1 0) (22 22 s9 0 0 0) (=== testing 10 ===) (0 22 s10 0 0 0) (1 22 s10 0 1 0) (2 22 s10 0 2 0) (3 22 s10 0 4 0) (4 22 s10 30 31 20) (5 22 s10 150 145 110) (6 22 s10 520 516 330) (7 22 s10 1290 1273 840) (8 22 s10 2990 2990 2050) (9 22 s10 5170 5161 3640) (10 22 s10 5980 5983 3860) (11 22 s10 8990 8974 6430) (12 22 s10 8880 8878 6330) (13 22 s10 7240 7231 5090) (14 22 s10 3860 3865 2340) (15 22 s10 2380 2373 1470) (16 22 s10 1400 1397 930) (17 22 s10 480 476 290) (18 22 s10 180 174 110) (19 22 s10 30 36 20) (20 22 s10 10 12 0) (21 22 s10 10 11 0) (22 22 s10 10 11 0) (=== testing 1 ===) (0 22 s1 0 0 0) (1 22 s1 0 0 0) (2 22 s1 0 2 0) (3 22 s1 10 14 0) (4 22 s1 70 69 0) (5 22 s1 390 388 110) (6 22 s1 1090 1092 270) (7 22 s1 2870 2871 870) (8 22 s1 6200 6177 2120) (9 22 s1 9500 9470 2700) (10 22 s1 14320 14314 4750) (11 22 s1 15900 15865 4490) (12 22 s1 17010 16999 5440) (13 22 s1 13550 13545 3700) (14 22 s1 9920 9912 2840) (15 22 s1 5760 5756 1500) (16 22 s1 2940 2929 780) (17 22 s1 1150 1144 270) (18 22 s1 360 361 50) (19 22 s1 90 90 10) (20 22 s1 20 16 0) (21 22 s1 10 3 0) (22 22 s1 0 0 0) (=== testing 2 ===) (0 22 s2 0 0 0) (1 22 s2 0 0 0) (2 22 s2 10 1 0) (3 22 s2 10 4 0) (4 22 s2 30 32 20) (5 22 s2 200 200 140) (6 22 s2 520 523 320) (7 22 s2 1920 1915 1360) (8 22 s2 4680 4671 3470) (9 22 s2 7090 7075 4880) (10 22 s2 11940 11930 8480) (11 22 s2 16400 16390 11610) (12 22 s2 19750 19769 13720) (13 22 s2 22320 22308 15380) (14 22 s2 22890 22884 15400) (15 22 s2 23090 23088 15360) (16 22 s2 23250 23218 15360) (17 22 s2 23290 23280 15430) (18 22 s2 23270 23258 15360) (19 22 s2 23260 23266 15370) (20 22 s2 23250 23251 15370) (21 22 s2 23240 23234 15340) (22 22 s2 23280 23268 15380) (=== testing 3 ===) (0 22 s3 0 0 0) (1 22 s3 0 0 0) (2 22 s3 0 1 0) (3 22 s3 0 3 0) (4 22 s3 40 39 20) (5 22 s3 150 154 90) (6 22 s3 660 655 460) (7 22 s3 1630 1628 1100) (8 22 s3 3170 3177 2020) (9 22 s3 6240 6223 4100) (10 22 s3 11050 11021 7600) (11 22 s3 13830 13838 9040) (12 22 s3 16450 16416 10410) (13 22 s3 18630 18596 11660) (14 22 s3 20430 20431 12850) (15 22 s3 20810 20768 12920) (16 22 s3 20940 20908 12890) (17 22 s3 20960 20956 12900) (18 22 s3 21010 20976 12910) (19 22 s3 20960 20947 12860) (20 22 s3 21000 20967 12910) (21 22 s3 21020 20979 12920) (22 22 s3 20930 20926 12850) (=== testing 4 ===) (0 22 s4 0 0 0) (1 22 s4 0 0 0) (2 22 s4 0 1 0) (3 22 s4 10 9 0) (4 22 s4 50 50 0) (5 22 s4 260 261 70) (6 22 s4 880 875 290) (7 22 s4 2350 2354 890) (8 22 s4 5180 5160 2130) (9 22 s4 7840 7805 2750) (10 22 s4 12060 12066 4830) (11 22 s4 13220 13200 4560) (12 22 s4 13330 13301 4560) (13 22 s4 11400 11363 3840) (14 22 s4 8320 8302 2840) (15 22 s4 4870 4873 1560) (16 22 s4 2500 2491 800) (17 22 s4 960 970 260) (18 22 s4 280 274 40) (19 22 s4 60 62 0) (20 22 s4 10 12 0) (21 22 s4 0 2 0) (22 22 s4 0 0 0) (=== testing 5 ===) (0 22 s5 0 0 0) (1 22 s5 0 0 0) (2 22 s5 0 0 0) (3 22 s5 0 7 0) (4 22 s5 80 77 30) (5 22 s5 510 513 280) (6 22 s5 2060 2056 1190) (7 22 s5 5590 5578 3160) (8 22 s5 13070 13077 7460) (9 22 s5 26060 26073 15340) (10 22 s5 41320 41304 24040) (11 22 s5 57980 57962 34090) (12 22 s5 63370 63391 34490) (13 22 s5 59520 59510 27910) (14 22 s5 52470 52455 20400) (15 22 s5 43930 43922 12480) (16 22 s5 38900 38875 8250) (17 22 s5 35600 35573 5550) (18 22 s5 33190 33174 3510) (19 22 s5 32320 32317 2770) (20 22 s5 31110 31093 1620) (21 22 s5 30530 30529 1310) (22 22 s5 30540 30515 1010) (=== testing 6 ===) (0 22 s6 0 0 0) (1 22 s6 0 0 0) (2 22 s6 0 1 0) (3 22 s6 10 3 0) (4 22 s6 20 26 10) (5 22 s6 140 137 90) (6 22 s6 490 488 340) (7 22 s6 1330 1336 970) (8 22 s6 2780 2778 2020) (9 22 s6 4540 4538 3280) (10 22 s6 8040 8018 6250) (11 22 s6 7340 7344 5270) (12 22 s6 7560 7559 5470) (13 22 s6 7620 7625 5860) (14 22 s6 5440 5438 4160) (15 22 s6 2820 2819 2080) (16 22 s6 1450 1455 1070) (17 22 s6 470 468 310) (18 22 s6 170 171 120) (19 22 s6 30 28 20) (20 22 s6 0 6 0) (21 22 s6 0 4 0) (22 22 s6 0 4 0) (=== testing 7 ===) (0 22 s7 0 0 0) (1 22 s7 0 1 0) (2 22 s7 0 1 0) (3 22 s7 0 3 0) (4 22 s7 30 27 10) (5 22 s7 140 138 90) (6 22 s7 490 488 330) (7 22 s7 1340 1335 980) (8 22 s7 2750 2750 1990) (9 22 s7 4540 4533 3270) (10 22 s7 7990 7998 6230) (11 22 s7 7360 7355 5300) (12 22 s7 8330 8332 6250) (13 22 s7 7620 7629 5830) (14 22 s7 5440 5441 4140) (15 22 s7 2820 2823 2070) (16 22 s7 1470 1459 1100) (17 22 s7 470 467 330) (18 22 s7 170 172 120) (19 22 s7 30 28 10) (20 22 s7 10 6 0) (21 22 s7 0 3 0) (22 22 s7 0 3 0) (=== testing 8 ===) (0 22 s8 0 0 0) (1 22 s8 0 1 0) (2 22 s8 0 1 0) (3 22 s8 10 7 0) (4 22 s8 30 35 0) (5 22 s8 200 203 70) (6 22 s8 660 662 240) (7 22 s8 1570 1571 540) (8 22 s8 3260 3258 1240) (9 22 s8 5300 5303 2020) (10 22 s8 8240 8220 3860) (11 22 s8 8650 8655 3770) (12 22 s8 8380 8375 3870) (13 22 s8 6840 6831 3380) (14 22 s8 3740 3738 1510) (15 22 s8 2170 2165 980) (16 22 s8 1130 1124 620) (17 22 s8 280 287 110) (18 22 s8 100 101 60) (19 22 s8 10 9 0) (20 22 s8 10 1 0) (21 22 s8 0 1 0) (22 22 s8 0 0 0) (=== testing 9 ===) (0 22 s9 0 0 0) (1 22 s9 0 0 0) (2 22 s9 0 1 0) (3 22 s9 10 7 0) (4 22 s9 40 39 20) (5 22 s9 320 319 240) (6 22 s9 920 921 680) (7 22 s9 2430 2431 1850) (8 22 s9 3480 3476 2440) (9 22 s9 6800 6792 5190) (10 22 s9 10460 10441 8370) (11 22 s9 9400 9399 7160) (12 22 s9 10420 10430 8340) (13 22 s9 6770 6770 5170) (14 22 s9 5020 5023 3970) (15 22 s9 2510 2495 1900) (16 22 s9 1000 986 650) (17 22 s9 470 469 310) (18 22 s9 150 152 70) (19 22 s9 50 43 10) (20 22 s9 10 10 0) (21 22 s9 10 1 0) (22 22 s9 0 0 0) (=== testing 10 ===) (0 22 s10 0 1 0) (1 22 s10 0 0 0) (2 22 s10 0 2 0) (3 22 s10 10 5 0) (4 22 s10 30 31 20) (5 22 s10 150 144 80) (6 22 s10 520 517 330) (7 22 s10 1280 1274 850) (8 22 s10 3000 2979 2080) (9 22 s10 5160 5160 3640) (10 22 s10 5970 5974 3830) (11 22 s10 8970 8973 6440) (12 22 s10 8890 8872 6350) (13 22 s10 7210 7227 5070) (14 22 s10 3870 3864 2330) (15 22 s10 2380 2378 1470) (16 22 s10 1400 1398 930) (17 22 s10 480 476 290) (18 22 s10 170 174 110) (19 22 s10 40 36 10) (20 22 s10 10 12 0) (21 22 s10 10 11 0) (22 22 s10 10 10 0) (=== testing 1 ===) (0 22 s1 0 0 0) (1 22 s1 0 0 0) (2 22 s1 0 2 0) (3 22 s1 20 14 0) (4 22 s1 60 69 0) (5 22 s1 400 390 110) (6 22 s1 1090 1094 280) (7 22 s1 2880 2868 880) (8 22 s1 6170 6169 2100) (9 22 s1 9480 9477 2670) (10 22 s1 14300 14301 4720) (11 22 s1 15870 15862 4430) (12 22 s1 17020 17006 5460) (13 22 s1 13550 13542 3740) (14 22 s1 9920 9911 2850) (15 22 s1 5770 5761 1500) (16 22 s1 2930 2930 760) (17 22 s1 1150 1145 250) (18 22 s1 360 359 60) (19 22 s1 80 89 10) (20 22 s1 10 16 0) (21 22 s1 0 2 0) (22 22 s1 0 0 0) (=== testing 2 ===) (0 22 s2 0 0 0) (1 22 s2 0 0 0) (2 22 s2 0 1 0) (3 22 s2 0 4 0) (4 22 s2 30 32 20) (5 22 s2 200 200 140) (6 22 s2 520 525 320) (7 22 s2 1920 1918 1360) (8 22 s2 4670 4672 3480) (9 22 s2 7070 7067 4890) (10 22 s2 11930 11932 8450) (11 22 s2 16430 16431 11610) (12 22 s2 19780 19782 13770) (13 22 s2 22310 22315 15360) (14 22 s2 22920 22897 15430) (15 22 s2 23120 23126 15390) (16 22 s2 23220 23220 15350) (17 22 s2 23310 23264 15440) (18 22 s2 23310 23261 15410) (19 22 s2 23320 23280 15390) (20 22 s2 23250 23245 15370) (21 22 s2 23380 23293 15460) (22 22 s2 23400 23397 15470) (=== testing 3 ===) (0 22 s3 0 0 0) (1 22 s3 0 0 0) (2 22 s3 0 0 0) (3 22 s3 0 3 0) (4 22 s3 40 39 20) (5 22 s3 150 156 90) (6 22 s3 670 669 450) (7 22 s3 1670 1671 1140) (8 22 s3 3200 3200 2060) (9 22 s3 6260 6239 4120) (10 22 s3 11050 11025 7660) (11 22 s3 13920 13868 9100) (12 22 s3 16530 16513 10560) (13 22 s3 18750 18710 11700) (14 22 s3 20550 20511 12960) (15 22 s3 20830 20785 12900) (16 22 s3 20940 20936 12860) (17 22 s3 21080 21053 12990) (18 22 s3 20940 20939 12920) (19 22 s3 20960 20948 12890) (20 22 s3 20960 20950 12880) (21 22 s3 20980 20976 12910) (22 22 s3 20960 20969 12850) (=== testing 4 ===) (0 22 s4 0 0 0) (1 22 s4 0 0 0) (2 22 s4 0 2 0) (3 22 s4 10 10 0) (4 22 s4 60 50 0) (5 22 s4 260 259 60) (6 22 s4 870 877 280) (7 22 s4 2350 2350 870) (8 22 s4 5170 5168 2150) (9 22 s4 7790 7813 2720) (10 22 s4 12120 12090 4880) (11 22 s4 13230 13230 4620) (12 22 s4 13500 13513 4640) (13 22 s4 11380 11372 3860) (14 22 s4 8300 8300 2880) (15 22 s4 4870 4870 1570) (16 22 s4 2480 2488 810) (17 22 s4 990 972 280) (18 22 s4 280 274 40) (19 22 s4 70 62 0) (20 22 s4 20 12 0) (21 22 s4 0 2 0) (22 22 s4 0 0 0) (=== testing 5 ===) (0 22 s5 0 0 0) (1 22 s5 0 0 0) (2 22 s5 0 0 0) (3 22 s5 10 7 0) (4 22 s5 80 77 30) (5 22 s5 510 510 280) (6 22 s5 2060 2061 1190) (7 22 s5 5640 5629 3170) (8 22 s5 13080 13080 7440) (9 22 s5 26100 26072 15360) (10 22 s5 41360 41359 24080) (11 22 s5 57960 57961 34030) (12 22 s5 63440 63427 34520) (13 22 s5 59560 59530 27930) (14 22 s5 52570 52608 20550) (15 22 s5 43900 43894 12510) (16 22 s5 38930 38871 8270) (17 22 s5 35590 35540 5560) (18 22 s5 33180 33204 3510) (19 22 s5 32320 32334 2770) (20 22 s5 31150 31097 1660) (21 22 s5 30530 30529 1320) (22 22 s5 30480 30474 1050) (=== testing 6 ===) (0 22 s6 0 0 0) (1 22 s6 0 0 0) (2 22 s6 0 1 0) (3 22 s6 0 3 0) (4 22 s6 30 26 20) (5 22 s6 130 139 90) (6 22 s6 490 490 360) (7 22 s6 1340 1337 960) (8 22 s6 2760 2777 2010) (9 22 s6 4530 4530 3300) (10 22 s6 8000 8007 6220) (11 22 s6 7360 7363 5280) (12 22 s6 7560 7561 5460) (13 22 s6 7620 7622 5830) (14 22 s6 5440 5434 4170) (15 22 s6 2820 2820 2070) (16 22 s6 1460 1458 1090) (17 22 s6 460 467 310) (18 22 s6 170 172 120) (19 22 s6 20 27 10) (20 22 s6 0 6 0) (21 22 s6 10 4 0) (22 22 s6 0 3 0) (=== testing 7 ===) (0 22 s7 0 0 0) (1 22 s7 0 1 0) (2 22 s7 0 1 0) (3 22 s7 0 3 0) (4 22 s7 30 26 10) (5 22 s7 140 138 100) (6 22 s7 490 488 340) (7 22 s7 1340 1339 970) (8 22 s7 2770 2763 2000) (9 22 s7 4520 4532 3280) (10 22 s7 8020 8015 6260) (11 22 s7 7350 7352 5280) (12 22 s7 8340 8321 6280) (13 22 s7 7630 7627 5820) (14 22 s7 5440 5439 4160) (15 22 s7 2820 2823 2080) (16 22 s7 1460 1458 1100) (17 22 s7 460 468 310) (18 22 s7 170 172 120) (19 22 s7 20 28 10) (20 22 s7 10 5 0) (21 22 s7 0 4 0) (22 22 s7 10 4 0) (=== testing 8 ===) (0 22 s8 0 0 0) (1 22 s8 0 0 0) (2 22 s8 0 1 0) (3 22 s8 0 6 0) (4 22 s8 30 35 0) (5 22 s8 200 204 70) (6 22 s8 660 662 240) (7 22 s8 1580 1571 550) (8 22 s8 3270 3261 1230) (9 22 s8 5310 5298 2030) (10 22 s8 8230 8221 3840) (11 22 s8 8690 8680 3800) (12 22 s8 8390 8373 3850) (13 22 s8 6830 6825 3360) (14 22 s8 3750 3742 1520) (15 22 s8 2160 2159 980) (16 22 s8 1140 1126 640) (17 22 s8 290 287 120) (18 22 s8 100 101 60) (19 22 s8 0 9 0) (20 22 s8 10 1 0) (21 22 s8 0 0 0) (22 22 s8 0 0 0) (=== testing 9 ===) (0 22 s9 0 0 0) (1 22 s9 0 0 0) (2 22 s9 0 1 0) (3 22 s9 0 7 0) (4 22 s9 30 39 10) (5 22 s9 320 320 240) (6 22 s9 930 922 670) (7 22 s9 2430 2427 1870) (8 22 s9 3480 3467 2450) (9 22 s9 6810 6803 5200) (10 22 s9 10460 10440 8410) (11 22 s9 9420 9407 7160) (12 22 s9 10470 10440 8380) (13 22 s9 6800 6785 5190) (14 22 s9 5040 5027 3970) (15 22 s9 2490 2490 1880) (16 22 s9 980 984 660) (17 22 s9 460 468 300) (18 22 s9 150 152 70) (19 22 s9 40 43 10) (20 22 s9 10 10 0) (21 22 s9 0 2 0) (22 22 s9 0 0 0) (=== testing 10 ===) (0 22 s10 0 0 0) (1 22 s10 10 1 0) (2 22 s10 0 2 0) (3 22 s10 10 4 0) (4 22 s10 30 31 10) (5 22 s10 150 144 70) (6 22 s10 510 517 330) (7 22 s10 1270 1273 860) (8 22 s10 2970 2980 2050) (9 22 s10 5150 5148 3610) (10 22 s10 5970 5969 3850) (11 22 s10 8970 8973 6450) (12 22 s10 8870 8864 6330) (13 22 s10 7230 7229 5110) (14 22 s10 3850 3861 2380) (15 22 s10 2380 2378 1490) (16 22 s10 1400 1397 940) (17 22 s10 470 475 300) (18 22 s10 170 175 110) (19 22 s10 40 36 10) (20 22 s10 10 13 0) (21 22 s10 10 10 0) (22 22 s10 10 10 0) (=== testing 1 ===) (0 22 s1 0 0 0) (1 22 s1 0 0 0) (2 22 s1 10 2 0) (3 22 s1 10 14 0) (4 22 s1 70 70 0) (5 22 s1 390 388 120) (6 22 s1 1090 1088 280) (7 22 s1 2870 2872 860) (8 22 s1 6200 6189 2110) (9 22 s1 9490 9471 2680) (10 22 s1 14310 14328 4750) (11 22 s1 15880 15872 4490) (12 22 s1 17030 17007 5460) (13 22 s1 13530 13525 3730) (14 22 s1 9920 9917 2820) (15 22 s1 5760 5762 1470) (16 22 s1 2930 2940 800) (17 22 s1 1150 1148 280) (18 22 s1 370 362 60) (19 22 s1 90 90 10) (20 22 s1 20 16 0) (21 22 s1 0 2 0) (22 22 s1 10 1 0) (=== testing 2 ===) (0 22 s2 0 0 0) (1 22 s2 0 0 0) (2 22 s2 10 1 0) (3 22 s2 0 4 0) (4 22 s2 30 33 10) (5 22 s2 200 200 130) (6 22 s2 520 525 310) (7 22 s2 1930 1918 1390) (8 22 s2 4690 4681 3490) (9 22 s2 7110 7105 4890) (10 22 s2 11990 11967 8550) (11 22 s2 16420 16418 11580) (12 22 s2 19770 19757 13770) (13 22 s2 22310 22308 15400) (14 22 s2 22840 22869 15370) (15 22 s2 23190 23207 15450) (16 22 s2 23300 23290 15430) (17 22 s2 23240 23239 15380) (18 22 s2 23260 23265 15400) (19 22 s2 23320 23278 15460) (20 22 s2 23440 23350 15530) (21 22 s2 23260 23246 15340) (22 22 s2 23520 23509 15580) (=== testing 3 ===) (0 22 s3 0 0 0) (1 22 s3 0 0 0) (2 22 s3 0 1 0) (3 22 s3 0 3 0) (4 22 s3 30 39 20) (5 22 s3 150 156 90) (6 22 s3 660 660 470) (7 22 s3 1640 1642 1120) (8 22 s3 3210 3217 2050) (9 22 s3 6290 6285 4150) (10 22 s3 11180 11177 7760) (11 22 s3 14070 14059 9240) (12 22 s3 16610 16624 10500) (13 22 s3 18910 18920 11910) (14 22 s3 20530 20526 12960) (15 22 s3 20800 20793 12910) (16 22 s3 21000 20999 12910) (17 22 s3 21080 21054 12980) (18 22 s3 21010 21006 12920) (19 22 s3 21100 21075 13000) (20 22 s3 21130 21082 13010) (21 22 s3 21030 21028 12940) (22 22 s3 20960 20950 12870) (=== testing 4 ===) (0 22 s4 0 0 0) (1 22 s4 0 0 0) (2 22 s4 0 1 0) (3 22 s4 10 10 0) (4 22 s4 50 50 0) (5 22 s4 260 260 60) (6 22 s4 870 874 280) (7 22 s4 2370 2355 880) (8 22 s4 5160 5158 2140) (9 22 s4 7810 7823 2740) (10 22 s4 12070 12067 4810) (11 22 s4 13230 13213 4560) (12 22 s4 13270 13270 4550) (13 22 s4 11360 11360 3830) (14 22 s4 8290 8298 2840) (15 22 s4 4860 4859 1550) (16 22 s4 2480 2484 810) (17 22 s4 970 969 280) (18 22 s4 280 275 40) (19 22 s4 60 62 0) (20 22 s4 20 12 0) (21 22 s4 0 2 0) (22 22 s4 0 0 0) (=== testing 5 ===) (0 22 s5 0 0 0) (1 22 s5 0 0 0) (2 22 s5 0 0 0) (3 22 s5 0 6 0) (4 22 s5 70 77 20) (5 22 s5 530 516 290) (6 22 s5 2060 2055 1220) (7 22 s5 5590 5590 3110) (8 22 s5 13080 13062 7450) (9 22 s5 26090 26065 15360) (10 22 s5 41350 41316 24140) (11 22 s5 58080 58012 34140) (12 22 s5 63410 63407 34510) (13 22 s5 59500 59512 27860) (14 22 s5 52590 52541 20410) (15 22 s5 43920 43932 12450) (16 22 s5 38890 38882 8270) (17 22 s5 35470 35553 5580) (18 22 s5 33230 33198 3540) (19 22 s5 32340 32312 2790) (20 22 s5 31120 31079 1670) (21 22 s5 30540 30534 1100) (22 22 s5 30460 30458 1050) (=== testing 6 ===) (0 22 s6 0 0 0) (1 22 s6 0 0 0) (2 22 s6 0 1 0) (3 22 s6 10 3 0) (4 22 s6 20 26 10) (5 22 s6 140 137 90) (6 22 s6 490 488 340) (7 22 s6 1330 1334 960) (8 22 s6 2770 2770 2020) (9 22 s6 4530 4526 3280) (10 22 s6 8000 8015 6260) (11 22 s6 7360 7359 5270) (12 22 s6 7580 7579 5470) (13 22 s6 7630 7632 5820) (14 22 s6 5420 5430 4150) (15 22 s6 2810 2818 2050) (16 22 s6 1460 1457 1080) (17 22 s6 460 467 310) (18 22 s6 170 171 120) (19 22 s6 30 28 10) (20 22 s6 10 6 0) (21 22 s6 10 4 0) (22 22 s6 0 4 0) (=== testing 7 ===) (0 22 s7 0 0 0) (1 22 s7 0 0 0) (2 22 s7 0 1 0) (3 22 s7 0 3 0) (4 22 s7 20 27 10) (5 22 s7 140 137 80) (6 22 s7 490 487 350) (7 22 s7 1330 1331 960) (8 22 s7 2770 2762 2010) (9 22 s7 4540 4532 3300) (10 22 s7 8020 8008 6250) (11 22 s7 7380 7355 5310) (12 22 s7 8330 8324 6240) (13 22 s7 7620 7622 5840) (14 22 s7 5430 5434 4160) (15 22 s7 2820 2819 2090) (16 22 s7 1460 1460 1100) (17 22 s7 470 468 320) (18 22 s7 170 172 120) (19 22 s7 30 27 20) (20 22 s7 10 6 0) (21 22 s7 10 3 0) (22 22 s7 0 4 0) (=== testing 8 ===) (0 22 s8 0 0 0) (1 22 s8 0 0 0) (2 22 s8 10 1 0) (3 22 s8 10 7 0) (4 22 s8 30 34 0) (5 22 s8 200 203 60) (6 22 s8 660 663 240) (7 22 s8 1580 1571 560) (8 22 s8 3270 3264 1240) (9 22 s8 5300 5303 2040) (10 22 s8 8220 8214 3850) (11 22 s8 8680 8671 3800) (12 22 s8 8420 8375 3870) (13 22 s8 6830 6829 3340) (14 22 s8 3730 3743 1510) (15 22 s8 2170 2165 980) (16 22 s8 1130 1128 610) (17 22 s8 280 289 110) (18 22 s8 100 100 50) (19 22 s8 10 9 0) (20 22 s8 0 1 0) (21 22 s8 0 0 0) (22 22 s8 0 0 0) (=== testing 9 ===) (0 22 s9 0 0 0) (1 22 s9 0 0 0) (2 22 s9 10 1 0) (3 22 s9 0 6 0) (4 22 s9 40 39 20) (5 22 s9 310 319 220) (6 22 s9 920 920 680) (7 22 s9 2430 2425 1860) (8 22 s9 3480 3470 2430) (9 22 s9 6800 6793 5160) (10 22 s9 10440 10436 8350) (11 22 s9 9400 9393 7170) (12 22 s9 10470 10446 8400) (13 22 s9 6780 6786 5160) (14 22 s9 5040 5031 3970) (15 22 s9 2490 2484 1890) (16 22 s9 980 982 650) (17 22 s9 470 468 320) (18 22 s9 150 152 80) (19 22 s9 50 43 10) (20 22 s9 10 10 0) (21 22 s9 10 2 0) (22 22 s9 0 0 0) (=== testing 10 ===) (0 22 s10 0 0 0) (1 22 s10 0 0 0) (2 22 s10 10 2 0) (3 22 s10 0 4 0) (4 22 s10 30 31 20) (5 22 s10 150 143 70) (6 22 s10 520 516 340) (7 22 s10 1270 1271 840) (8 22 s10 2980 2977 2070) (9 22 s10 5150 5147 3630) (10 22 s10 5990 5964 3870) (11 22 s10 8990 8965 6440) (12 22 s10 8870 8866 6320) (13 22 s10 7230 7221 5060) (14 22 s10 3860 3858 2360) (15 22 s10 2380 2376 1480) (16 22 s10 1410 1401 940) (17 22 s10 480 476 290) (18 22 s10 170 174 110) (19 22 s10 40 36 10) (20 22 s10 20 13 0) (21 22 s10 10 11 0) (22 22 s10 10 11 0) (=== testing 1 ===) (0 22 s1 0 0 0) (1 22 s1 0 0 0) (2 22 s1 0 2 0) (3 22 s1 10 13 0) (4 22 s1 70 70 0) (5 22 s1 380 386 110) (6 22 s1 1080 1085 280) (7 22 s1 2870 2879 880) (8 22 s1 6180 6175 2120) (9 22 s1 9480 9463 2670) (10 22 s1 14360 14351 4720) (11 22 s1 15830 15835 4440) (12 22 s1 17010 16983 5480) (13 22 s1 13530 13511 3690) (14 22 s1 9930 9919 2870) (15 22 s1 5760 5753 1490) (16 22 s1 2930 2932 790) (17 22 s1 1160 1147 280) (18 22 s1 360 361 70) (19 22 s1 90 89 10) (20 22 s1 20 16 0) (21 22 s1 0 2 0) (22 22 s1 0 0 0) (=== testing 2 ===) (0 22 s2 0 0 0) (1 22 s2 0 0 0) (2 22 s2 10 1 0) (3 22 s2 10 4 0) (4 22 s2 30 32 20) (5 22 s2 200 200 130) (6 22 s2 520 522 310) (7 22 s2 1920 1915 1360) (8 22 s2 4670 4666 3500) (9 22 s2 7080 7072 4880) (10 22 s2 11870 11923 8470) (11 22 s2 16420 16410 11590) (12 22 s2 19740 19733 13750) (13 22 s2 22260 22264 15360) (14 22 s2 22840 22846 15390) (15 22 s2 23110 23105 15360) (16 22 s2 23230 23219 15380) (17 22 s2 23240 23229 15350) (18 22 s2 23310 23246 15410) (19 22 s2 23240 23248 15360) (20 22 s2 23320 23321 15430) (21 22 s2 23260 23242 15380) (22 22 s2 23280 23255 15390) (=== testing 3 ===) (0 22 s3 0 0 0) (1 22 s3 0 0 0) (2 22 s3 0 0 0) (3 22 s3 0 3 0) (4 22 s3 40 38 20) (5 22 s3 160 154 100) (6 22 s3 670 659 450) (7 22 s3 1630 1633 1090) (8 22 s3 3170 3170 2040) (9 22 s3 6220 6218 4090) (10 22 s3 11020 11026 7700) (11 22 s3 13850 13854 9090) (12 22 s3 16430 16410 10410) (13 22 s3 18600 18594 11660) (14 22 s3 20490 20450 12920) (15 22 s3 20800 20778 12900) (16 22 s3 20930 20911 12890) (17 22 s3 20950 20941 12930) (18 22 s3 21040 21003 12900) (19 22 s3 20990 21008 12910) (20 22 s3 21020 21011 12910) (21 22 s3 21020 21000 12860) (22 22 s3 20980 20979 12940) (=== testing 4 ===) (0 22 s4 0 0 0) (1 22 s4 0 1 0) (2 22 s4 0 1 0) (3 22 s4 10 10 0) (4 22 s4 60 51 0) (5 22 s4 260 260 70) (6 22 s4 880 878 290) (7 22 s4 2360 2354 890) (8 22 s4 5160 5158 2120) (9 22 s4 7820 7815 2740) (10 22 s4 12050 12058 4830) (11 22 s4 13250 13206 4590) (12 22 s4 13280 13291 4540) (13 22 s4 11350 11349 3830) (14 22 s4 8290 8286 2840) (15 22 s4 4870 4867 1610) (16 22 s4 2480 2487 810) (17 22 s4 980 971 280) (18 22 s4 270 275 50) (19 22 s4 60 62 0) (20 22 s4 10 12 0) (21 22 s4 0 2 0) (22 22 s4 0 1 0) (=== testing 5 ===) (0 22 s5 0 0 0) (1 22 s5 0 0 0) (2 22 s5 0 0 0) (3 22 s5 10 7 0) (4 22 s5 90 78 30) (5 22 s5 510 511 280) (6 22 s5 2050 2056 1200) (7 22 s5 5590 5577 3150) (8 22 s5 13110 13079 7510) (9 22 s5 26060 26050 15290) (10 22 s5 41280 41279 24010) (11 22 s5 58010 57972 34070) (12 22 s5 63400 63402 34450) (13 22 s5 59510 59510 27870) (14 22 s5 52440 52431 20330) (15 22 s5 43990 43952 12460) (16 22 s5 38910 38882 8270) (17 22 s5 35530 35530 5520) (18 22 s5 33120 33123 3530) (19 22 s5 32260 32260 2780) (20 22 s5 31020 31045 1620) (21 22 s5 30550 30527 1360) (22 22 s5 30430 30436 1120) (=== testing 6 ===) (0 22 s6 0 0 0) (1 22 s6 0 0 0) (2 22 s6 0 1 0) (3 22 s6 10 2 0) (4 22 s6 20 26 10) (5 22 s6 140 137 80) (6 22 s6 490 488 360) (7 22 s6 1340 1333 980) (8 22 s6 2780 2770 2000) (9 22 s6 4530 4526 3300) (10 22 s6 8020 8017 6220) (11 22 s6 7340 7343 5270) (12 22 s6 7560 7561 5460) (13 22 s6 7620 7620 5850) (14 22 s6 5430 5426 4150) (15 22 s6 2820 2822 2060) (16 22 s6 1450 1454 1070) (17 22 s6 470 467 330) (18 22 s6 170 172 120) (19 22 s6 30 28 10) (20 22 s6 10 5 0) (21 22 s6 0 4 0) (22 22 s6 0 4 0) (=== testing 7 ===) (0 22 s7 0 0 0) (1 22 s7 0 0 0) (2 22 s7 0 1 0) (3 22 s7 0 3 0) (4 22 s7 30 26 20) (5 22 s7 140 137 90) (6 22 s7 480 488 340) (7 22 s7 1340 1331 950) (8 22 s7 2750 2749 1990) (9 22 s7 4530 4525 3290) (10 22 s7 7990 7996 6220) (11 22 s7 7380 7360 5300) (12 22 s7 8320 8319 6230) (13 22 s7 7620 7623 5840) (14 22 s7 5430 5430 4150) (15 22 s7 2830 2825 2070) (16 22 s7 1470 1458 1090) (17 22 s7 480 469 340) (18 22 s7 170 173 130) (19 22 s7 30 28 20) (20 22 s7 0 5 0) (21 22 s7 0 4 0) (22 22 s7 10 4 0) (=== testing 8 ===) (0 22 s8 0 0 0) (1 22 s8 0 0 0) (2 22 s8 0 1 0) (3 22 s8 0 7 0) (4 22 s8 40 35 0) (5 22 s8 200 203 60) (6 22 s8 660 663 250) (7 22 s8 1570 1570 540) (8 22 s8 3260 3254 1220) (9 22 s8 5330 5301 2040) (10 22 s8 8220 8212 3860) (11 22 s8 8650 8667 3780) (12 22 s8 8390 8368 3880) (13 22 s8 6830 6824 3360) (14 22 s8 3740 3741 1500) (15 22 s8 2170 2161 960) (16 22 s8 1130 1126 630) (17 22 s8 290 289 120) (18 22 s8 100 100 50) (19 22 s8 20 10 0) (20 22 s8 0 2 0) (21 22 s8 0 0 0) (22 22 s8 0 0 0) (=== testing 9 ===) (0 22 s9 0 0 0) (1 22 s9 0 0 0) (2 22 s9 0 1 0) (3 22 s9 10 7 0) (4 22 s9 30 39 10) (5 22 s9 310 318 220) (6 22 s9 930 921 670) (7 22 s9 2440 2432 1850) (8 22 s9 3500 3474 2460) (9 22 s9 6790 6793 5180) (10 22 s9 10420 10436 8350) (11 22 s9 9390 9402 7130) (12 22 s9 10450 10444 8380) (13 22 s9 6790 6780 5190) (14 22 s9 5040 5032 3950) (15 22 s9 2490 2489 1860) (16 22 s9 980 982 640) (17 22 s9 460 468 300) (18 22 s9 160 151 70) (19 22 s9 50 42 10) (20 22 s9 10 9 0) (21 22 s9 0 1 0) (22 22 s9 0 0 0) (=== testing 10 ===) (0 22 s10 0 0 0) (1 22 s10 0 1 0) (2 22 s10 0 2 0) (3 22 s10 0 4 0) (4 22 s10 40 32 20) (5 22 s10 140 143 90) (6 22 s10 520 516 340) (7 22 s10 1270 1272 830) (8 22 s10 2980 2976 2050) (9 22 s10 5150 5147 3640) (10 22 s10 5960 5969 3840) (11 22 s10 8980 8969 6450) (12 22 s10 8870 8876 6340) (13 22 s10 7220 7226 5080) (14 22 s10 3860 3856 2340) (15 22 s10 2380 2378 1470) (16 22 s10 1400 1396 940) (17 22 s10 470 478 300) (18 22 s10 170 174 110) (19 22 s10 30 37 20) (20 22 s10 20 12 0) (21 22 s10 10 10 0) (22 22 s10 10 11 0) (=== testing 1 ===) (0 22 s1 0 0 0) (1 22 s1 0 1 0) (2 22 s1 0 2 0) (3 22 s1 10 14 0) (4 22 s1 70 70 0) (5 22 s1 370 389 120) (6 22 s1 1090 1086 290) (7 22 s1 2880 2875 860) (8 22 s1 6200 6183 2120) (9 22 s1 9480 9478 2670) (10 22 s1 14330 14321 4720) (11 22 s1 15880 15846 4470) (12 22 s1 16970 16972 5470) (13 22 s1 13510 13497 3690) (14 22 s1 9900 9892 2830) (15 22 s1 5780 5758 1490) (16 22 s1 2930 2933 780) (17 22 s1 1140 1144 260) (18 22 s1 360 361 70) (19 22 s1 90 89 10) (20 22 s1 20 16 0) (21 22 s1 10 2 0) (22 22 s1 0 0 0) (=== testing 2 ===) (0 22 s2 0 0 0) (1 22 s2 0 0 0) (2 22 s2 0 0 0) (3 22 s2 0 4 0) (4 22 s2 30 32 20) (5 22 s2 220 202 140) (6 22 s2 530 522 310) (7 22 s2 1930 1918 1380) (8 22 s2 4670 4666 3500) (9 22 s2 7080 7078 4870) (10 22 s2 11930 11917 8510) (11 22 s2 16400 16397 11640) (12 22 s2 19780 19744 13750) (13 22 s2 22310 22290 15350) (14 22 s2 22810 22809 15370) (15 22 s2 23130 23102 15380) (16 22 s2 23240 23216 15360) (17 22 s2 23240 23234 15350) (18 22 s2 23330 23263 15400) (19 22 s2 23340 23271 15420) (20 22 s2 23260 23245 15320) (21 22 s2 23290 23261 15390) (22 22 s2 23270 23249 15380) (=== testing 3 ===) (0 22 s3 0 0 0) (1 22 s3 0 0 0) (2 22 s3 0 1 0) (3 22 s3 0 3 0) (4 22 s3 30 38 20) (5 22 s3 150 155 100) (6 22 s3 660 655 450) (7 22 s3 1620 1626 1120) (8 22 s3 3190 3179 2050) (9 22 s3 6240 6224 4130) (10 22 s3 11050 11039 7650) (11 22 s3 13870 13838 9110) (12 22 s3 16410 16403 10440) (13 22 s3 18650 18605 11700) (14 22 s3 20540 20505 12910) (15 22 s3 20960 20952 13010) (16 22 s3 20900 20898 12910) (17 22 s3 20970 20979 12920) (18 22 s3 20940 20946 12870) (19 22 s3 20970 20965 12880) (20 22 s3 20980 20964 12940) (21 22 s3 20960 20959 12910) (22 22 s3 20990 20984 12920) (=== testing 4 ===) (0 22 s4 0 0 0) (1 22 s4 0 0 0) (2 22 s4 0 1 0) (3 22 s4 10 10 0) (4 22 s4 50 50 0) (5 22 s4 260 260 60) (6 22 s4 870 872 290) (7 22 s4 2360 2354 900) (8 22 s4 5160 5161 2130) (9 22 s4 7830 7824 2730) (10 22 s4 12130 12084 4880) (11 22 s4 13230 13208 4580) (12 22 s4 13300 13296 4560) (13 22 s4 11360 11353 3830) (14 22 s4 8310 8296 2890) (15 22 s4 4870 4864 1570) (16 22 s4 2490 2489 810) (17 22 s4 970 968 290) (18 22 s4 270 274 50) (19 22 s4 70 62 0) (20 22 s4 10 13 0) (21 22 s4 0 2 0) (22 22 s4 0 0 0) (=== testing 5 ===) (0 22 s5 0 0 0) (1 22 s5 0 0 0) (2 22 s5 0 1 0) (3 22 s5 10 6 0) (4 22 s5 80 77 20) (5 22 s5 510 511 280) (6 22 s5 2060 2054 1200) (7 22 s5 5580 5580 3150) (8 22 s5 13090 13073 7490) (9 22 s5 26070 26045 15320) (10 22 s5 41250 41242 24000) (11 22 s5 57960 57946 34030) (12 22 s5 63380 63379 34490) (13 22 s5 59500 59501 27910) (14 22 s5 52540 52512 20400) (15 22 s5 43930 43925 12480) (16 22 s5 38820 38808 8260) (17 22 s5 35490 35497 5530) (18 22 s5 33190 33182 3450) (19 22 s5 32340 32337 2830) (20 22 s5 31130 31104 1650) (21 22 s5 30550 30542 1210) (22 22 s5 30590 30507 1120) (=== testing 6 ===) (0 22 s6 0 0 0) (1 22 s6 0 0 0) (2 22 s6 0 1 0) (3 22 s6 0 3 0) (4 22 s6 30 26 20) (5 22 s6 140 138 90) (6 22 s6 490 490 340) (7 22 s6 1330 1334 950) (8 22 s6 2790 2772 2020) (9 22 s6 4540 4536 3290) (10 22 s6 8050 8037 6260) (11 22 s6 7380 7362 5310) (12 22 s6 7570 7575 5480) (13 22 s6 7640 7635 5860) (14 22 s6 5430 5432 4150) (15 22 s6 2820 2821 2080) (16 22 s6 1460 1455 1080) (17 22 s6 480 470 340) (18 22 s6 170 171 120) (19 22 s6 30 27 10) (20 22 s6 10 6 0) (21 22 s6 10 4 0) (22 22 s6 0 4 0) (=== testing 7 ===) (0 22 s7 0 0 0) (1 22 s7 0 0 0) (2 22 s7 0 1 0) (3 22 s7 0 3 0) (4 22 s7 30 27 20) (5 22 s7 150 138 100) (6 22 s7 490 489 340) (7 22 s7 1350 1337 970) (8 22 s7 2760 2751 2000) (9 22 s7 4530 4531 3280) (10 22 s7 8060 8023 6310) (11 22 s7 7380 7360 5320) (12 22 s7 8370 8336 6300) (13 22 s7 7650 7636 5860) (14 22 s7 5430 5434 4160) (15 22 s7 2810 2817 2060) (16 22 s7 1470 1460 1090) (17 22 s7 470 467 330) (18 22 s7 180 172 130) (19 22 s7 30 28 10) (20 22 s7 0 6 0) (21 22 s7 0 4 0) (22 22 s7 0 4 0) (=== testing 8 ===) (0 22 s8 0 0 0) (1 22 s8 0 0 0) (2 22 s8 0 1 0) (3 22 s8 10 7 0) (4 22 s8 40 35 0) (5 22 s8 200 203 60) (6 22 s8 660 663 250) (7 22 s8 1570 1570 540) (8 22 s8 3280 3261 1240) (9 22 s8 5300 5294 2020) (10 22 s8 8230 8225 3840) (11 22 s8 8680 8664 3810) (12 22 s8 8390 8372 3880) (13 22 s8 6820 6829 3340) (14 22 s8 3730 3734 1530) (15 22 s8 2160 2158 980) (16 22 s8 1130 1125 640) (17 22 s8 290 287 120) (18 22 s8 100 100 60) (19 22 s8 10 10 0) (20 22 s8 0 2 0) (21 22 s8 0 0 0) (22 22 s8 0 0 0) (=== testing 9 ===) (0 22 s9 0 0 0) (1 22 s9 0 0 0) (2 22 s9 0 2 0) (3 22 s9 0 7 0) (4 22 s9 40 38 10) (5 22 s9 320 318 240) (6 22 s9 940 923 690) (7 22 s9 2440 2427 1870) (8 22 s9 3500 3475 2460) (9 22 s9 6780 6781 5170) (10 22 s9 10420 10431 8370) (11 22 s9 9400 9392 7150) (12 22 s9 10440 10430 8380) (13 22 s9 6780 6776 5170) (14 22 s9 5050 5029 3990) (15 22 s9 2490 2485 1870) (16 22 s9 990 983 640) (17 22 s9 470 471 290) (18 22 s9 160 152 80) (19 22 s9 40 43 10) (20 22 s9 10 10 0) (21 22 s9 0 2 0) (22 22 s9 0 0 0) (=== testing 10 ===) (0 22 s10 0 0 0) (1 22 s10 0 1 0) (2 22 s10 0 2 0) (3 22 s10 0 4 0) (4 22 s10 30 31 20) (5 22 s10 140 145 90) (6 22 s10 520 516 350) (7 22 s10 1270 1270 830) (8 22 s10 2990 2978 2070) (9 22 s10 5160 5155 3630) (10 22 s10 5970 5969 3860) (11 22 s10 9010 8980 6480) (12 22 s10 8860 8879 6330) (13 22 s10 7230 7224 5080) (14 22 s10 3850 3855 2350) (15 22 s10 2360 2374 1470) (16 22 s10 1400 1397 960) (17 22 s10 480 476 280) (18 22 s10 180 174 100) (19 22 s10 30 36 20) (20 22 s10 10 12 0) (21 22 s10 10 11 0) (22 22 s10 10 11 0) ))) (define alist '()) (define (add! num len sym cpu real gc) (let ((al (assq sym alist))) (unless al (set! al (list sym)) (set! alist (cons al alist))) (let ((n (assq num (cdr al)))) (unless n (set! n (list num)) (set-cdr! al (cons n (cdr al)))) (append! n (list (list cpu gc real)))))) (for-each (lambda (x) (when (= 6 (length x)) (apply add! x))) r) (map (lambda (al) (cons (car al) (map (lambda (x) (cons (car x) (let loop ((t (cddr x)) (s (cadr x))) (if (null? t) (map (lambda (y) (/ y (length (cdr x)))) s) (loop (cdr t) (map + s (car t))))))) (reverse! (cdr al))))) (reverse! alist)))) (define gnuplot (process*/ports (open-output-file "/dev/null" 'truncate) #f (current-error-port) "/usr/bin/gnuplot")) (parameterize ((current-output-port (cadr gnuplot))) (define (draw name func) (define 1st? #t) (define file (string-append "subsets-" (regexp-replace* "( +| *time)" (list->string (map char-downcase (string->list name))) "") ".png")) (printf "set terminal png color~%set output ~s~%set title '~a'~%~%plot " file name) (for-each (lambda (al) (if 1st? (set! 1st? #f) (printf ", ")) (printf "'-' t '~s' w l" (cadr (assq (car al) names)))) results) (newline) (for-each (lambda (al) (newline) (for-each (lambda (x) (printf "~a ~a~%" (car x) (round (apply func (cdr x))))) (cdr al)) (printf "e~%")) results) (eprintf "Making ~s...~%" file)) (draw "CPU Time" (lambda (cpu gc real) cpu)) (draw "GC Time" (lambda (cpu gc real) gc)) (draw "CPU - GC Time" (lambda (cpu gc real) (- cpu gc))) (draw "REAL - CPU Time" (lambda (cpu gc real) (- real cpu))) (set! results (cdr (cddddr results))) (draw "CPU Time - last 5" (lambda (cpu gc real) cpu)) (draw "GC Time - last 5" (lambda (cpu gc real) gc)) (draw "CPU - GC Time - last 5" (lambda (cpu gc real) (- cpu gc))) (printf "exit~%")) (define (count! l) (define c 0) (define !! (list '!!)) (let loop ((l l)) (if (and (pair? l) (not (eq? (car l) !!))) (let ((x (car l)) (y (cdr l))) (set-car! l !!) (set! c (+ 1 c)) (loop x) (loop y)) 0)) c)