(use srfi.13) ; string (use srfi.42) ; list-ec (use srfi.197) ; chain (use data.queue) (use gauche.collection) (use gauche.dictionary) (use gauche.generator) (use gauche.sequence) (use scheme.list) (use scheme.vector) (use util.match) (define input read-line) (define (ii) (string->number (input))) (define (li) (let ((s (input))) (map string->number (string-split s " ")))) (define-method prn* ((seq )) (for-each-with-index (^(i x) (when (> i 0) (display " ")) (display x)) seq) (newline)) (define (prn . args) (prn* args)) (define (prn-yn b) (prn (if b "Yes" "No"))) (define-syntax ->/prn (syntax-rules () ((_ x fns ...) (-> x fns ... prn)))) (define-syntax prn/d (syntax-rules () ((_ expr ...) (with-output-to-port (current-error-port) (^() (prn expr ...)))))) (define-syntax let/g (syntax-rules () ((_ var body ...) (generate (lambda (var) body ...))))) (define ord char->integer) (define chr integer->char) (define int string->number) (define str x->string) (define string* (apply$ string)) (define-method min ((xs )) (fold min (~ xs 0) xs)) (define-method max ((xs )) (fold max (~ xs 0) xs)) (define (minmax . xs) (values->list (apply min&max xs))) (define-method minmax ((xs )) (values->list (apply min&max xs))) (define (sum xs) (fold + 0 xs)) (define (divmod a b) (values->list (div-and-mod a b))) (define (ceildiv a b) (div (+ a (1- b)) b)) (define (1+ n) (+ n 1)) (define (1- n) (- n 1)) (define (!= a b) (not (= a b))) (define (midpoint a b) (div (+ a b) 2)) (define pow (case-lambda ((a b) (expt a b)) ((a b m) (expt-mod a b m)))) (define gcd* (apply$ gcd)) (define sq square) (define isqrt exact-integer-sqrt) (define pos? positive?) (define neg? negative?) (define (cmp< a b) (< (compare a b) 0)) (define (cmp> a b) (> (compare a b) 0)) (define ++ string-append) (define zip (map$ list)) (define all every) (define any-ec any?-ec) (define all-ec every?-ec) (define concat concatenate) (define foldl fold-left) (define (pairwise xs) (zip xs (cdr xs))) (define (comb n k) (if (or (< k 0) (> k n)) 0 (let loop ((i 0) (x 1)) (if (= i k) x (loop (1+ i) (div (* x (- n i)) (1+ i))))))) (define-method frequencies ((xs )) (let1 ht (make-hash-table equal-comparator) (for-each (^x (hash-table-update! ht x 1+ 0)) xs) (new ht))) ;; '(a b c) -> op(op(op(init, a), b), c) (define (scanl op init xs) (define (f a b) (let1 t (op b a) (values t t))) (map-accum f init xs)) ;;'(a b c) -> op(a, op(b, op(c, init))) (define (scanr op init xs) (define (f a b) (let1 t (op a b) (values t t))) (reverse (map-accum f init (reverse xs)))) (define-macro (input! vars . body) (let ((binds (map (^x (cond ((symbol? x) `((,x) (values (ii)))) ((list? x) (if (= 1 (length x)) `(,x (values (li))) `(,x (apply values (li))))) (else (error "symbol or list required, but got:" x)))) vars))) `(let*-values ,binds ,@body))) (define-macro (! self quoted-name . args) (let ((name (cadr quoted-name))) `(,name ,self ,@args))) (define-macro (d/ . args) (let ((ss (map (^(expr) `(list ,(x->string expr) ,expr)) args))) `(prn/d (list ,@ss)))) (define mlet match-let) (define mlet* match-let*) (define mlet1 match-let1) (define-macro (mfn pat . body) (let ((args (gensym))) `(lambda ,args (mlet1 ,pat ,args ,@body)))) (define-macro (mfn1 pat . body) (let ((arg (gensym))) `(lambda (,arg) (mlet1 ,pat ,arg ,@body)))) (define-method len ((coll )) (size-of coll)) (define (digits n) (map digit->integer (str n))) (define (digits->int ds) (fold-left (^(a b) (+ (* 10 a) b)) 0 ds)) (define (-> x . fns) (call-with-values (^() (values x)) (apply compose (reverse fns)))) (define (rep n thunk) (list-ec (: _ n) (thunk))) (define (memoize fn) (let ((cache (make-hash-table 'equal?))) (lambda args (if (hash-table-exists? cache args) (hash-table-get cache args) (let ((val (apply fn args))) (hash-table-put! cache args val) val))))) (define (zip-longest . args) (let* ((n (apply max (map length args))) (xxs (map (^(xs) (append xs (make-list (- n (length xs)) #f))) args))) (map (pa$ delete #f) (apply zip xxs)))) (define (accumulate xs) (list->vector (scan-left + 0 xs))) (define (accum xs) (let ((vs (accumulate xs))) (case-lambda ((l r) ; [l, r] (- (~ vs r) (if (> l 0) (~ vs (1- l)) 0))) ((r) ; [0, r] (~ vs r))))) (define (string->set s) (list->set eqv-comparator (string->list s))) (define (difference xs ys) (let ((excludes (list->set ys))) (filter (^x (not (set-contains? excludes x))) xs))) (define (uniq xs) (let1 ht (make-hash-table 'equal?) (for-each (^x (hash-table-put! ht x #t)) xs) (hash-table-keys ht))) ;; (define (make-dict) (new (make-hash-table equal-comparator))) (define-method new ((self )) (match-lambda* (('get key) (hash-table-get self key 0)) (('get key default) (hash-table-get self key default)) (('put! key value) (hash-table-put! self key value)) (('update! key proc) (hash-table-update! self key proc 0)) (('update! key proc default) (hash-table-update! self key proc default)) (('push! key value) (hash-table-push! self key value)) (('keys) (hash-table-keys self)) (('values) (hash-table-values self)) (('contains? key) (hash-table-contains? self key)) (('items) (hash-table->alist self)) (('map fn) (hash-table-map self fn)))) (define (alist->dict alist) (new (alist->hash-table alist equal-comparator))) (input! (N) (-> (~ (str N) 0) (^c (or (eqv? c #\4) (eqv? c #\5))) prn-yn))