Artifact e21b6366bf8728d909d8ce92c75ec4634a173022:
0000: 23 23 23 23 23 23 23 23 23 23 23 23 23 23 23 23 ################
0010: 23 23 23 23 23 23 23 23 23 23 23 23 23 23 23 23 ################
0020: 23 23 23 23 23 23 23 23 23 23 23 23 23 23 23 23 ################
0030: 23 23 23 23 23 23 23 23 23 23 23 23 23 23 23 23 ################
0040: 23 23 23 23 23 23 23 23 23 23 23 23 23 0a 23 20 #############.#
0050: 57 72 69 74 74 65 6e 20 69 6e 0a 23 20 20 20 20 Written in.#
0060: 42 6c 75 65 20 31 2e 37 2e 35 0a 23 20 20 20 20 Blue 1.7.5.#
0070: 68 74 74 70 3a 2f 2f 77 77 77 2e 6c 65 63 68 61 http://www.lecha
0080: 6b 2e 69 6e 66 6f 2f 62 6c 75 65 2f 0a 23 23 23 k.info/blue/.###
0090: 23 23 23 23 23 23 23 23 23 23 23 23 23 23 23 23 ################
00a0: 23 23 23 23 23 23 23 23 23 23 23 23 23 23 23 23 ################
00b0: 23 23 23 23 23 23 23 23 23 23 23 23 23 23 23 23 ################
00c0: 23 23 23 23 23 23 23 23 23 23 23 23 23 23 23 23 ################
00d0: 23 23 23 23 23 23 23 23 23 23 0a 0a 67 6c 6f 62 ##########..glob
00e0: 61 6c 20 46 52 4f 4d 5f 53 54 52 49 4e 47 20 3d al FROM_STRING =
00f0: 20 66 75 6e 63 20 7b 0a 09 61 72 67 20 73 3b 0a func {..arg s;.
0100: 0a 09 61 20 3d 20 5b 5d 3b 0a 09 69 20 3d 20 30 ..a = [];..i = 0
0110: 3b 0a 09 6c 6f 6f 70 20 7b 0a 09 09 61 20 3d 20 ;..loop {...a =
0120: 61 2e 61 70 70 65 6e 64 28 20 73 2e 73 75 62 73 a.append( s.subs
0130: 74 72 28 69 2c 69 2b 31 29 2e 6e 75 6d 28 29 20 tr(i,i+1).num()
0140: 29 3b 0a 09 09 28 69 3d 69 2b 31 29 20 3e 3d 20 );...(i=i+1) >=
0150: 73 2e 6c 65 6e 67 74 68 28 29 20 3f 20 72 65 74 s.length() ? ret
0160: 75 72 6e 3b 0a 09 7d 3b 0a 09 72 65 74 75 72 6e urn;..};..return
0170: 20 61 3b 0a 7d 3b 0a 0a 67 6c 6f 62 61 6c 20 54 a;.};..global T
0180: 4f 5f 53 54 52 49 4e 47 20 3d 20 66 75 6e 63 20 O_STRING = func
0190: 7b 0a 09 61 72 67 20 78 3b 0a 09 6c 65 78 69 63 {..arg x;..lexic
01a0: 61 6c 20 73 20 3d 20 22 22 3b 0a 09 78 2e 6d 61 al s = "";..x.ma
01b0: 70 28 20 66 75 6e 63 7b 20 73 20 3d 20 73 20 2b p( func{ s = s +
01c0: 20 74 68 69 73 3b 20 7d 20 29 3b 0a 09 72 65 74 this; } );..ret
01d0: 75 72 6e 20 73 3b 0a 7d 3b 0a 0a 67 6c 6f 62 61 urn s;.};..globa
01e0: 6c 20 4c 45 53 53 20 3d 20 66 75 6e 63 20 7b 0a l LESS = func {.
01f0: 09 61 72 67 20 78 3b 0a 09 61 72 67 20 79 3b 0a .arg x;..arg y;.
0200: 0a 09 78 6c 20 3d 20 78 2e 6c 65 6e 67 74 68 28 ..xl = x.length(
0210: 29 3b 0a 09 79 6c 20 3d 20 79 2e 6c 65 6e 67 74 );..yl = y.lengt
0220: 68 28 29 3b 0a 09 28 78 6c 20 3c 20 79 6c 29 20 h();..(xl < yl)
0230: 3f 20 72 65 74 75 72 6e 20 31 3b 0a 09 28 78 6c ? return 1;..(xl
0240: 20 3e 20 79 6c 29 20 3f 20 72 65 74 75 72 6e 20 > yl) ? return
0250: 30 3b 0a 09 69 20 3d 20 30 3b 0a 09 72 65 74 75 0;..i = 0;..retu
0260: 72 6e 20 6c 6f 6f 70 20 7b 0a 09 09 28 69 20 3d rn loop {...(i =
0270: 3d 20 78 6c 29 20 20 20 20 20 3f 20 72 65 74 75 = xl) ? retu
0280: 72 6e 20 30 3b 0a 09 09 28 78 5b 69 5d 20 3c 20 rn 0;...(x[i] <
0290: 79 5b 69 5d 29 20 3f 20 72 65 74 75 72 6e 20 31 y[i]) ? return 1
02a0: 3b 0a 09 09 28 78 5b 69 5d 20 3e 20 79 5b 69 5d ;...(x[i] > y[i]
02b0: 29 20 3f 20 72 65 74 75 72 6e 20 30 3b 0a 09 09 ) ? return 0;...
02c0: 69 20 3d 20 69 2b 31 3b 0a 09 7d 3b 0a 7d 3b 0a i = i+1;..};.};.
02d0: 0a 67 6c 6f 62 61 6c 20 53 55 42 20 3d 20 66 75 .global SUB = fu
02e0: 6e 63 20 7b 0a 09 61 72 67 20 78 3b 0a 09 61 72 nc {..arg x;..ar
02f0: 67 20 79 3b 0a 0a 09 78 2e 6c 65 6e 67 74 68 28 g y;...x.length(
0300: 29 20 3e 20 79 2e 6c 65 6e 67 74 68 28 29 20 3f ) > y.length() ?
0310: 20 28 79 20 3d 20 5b 5d 2e 72 65 73 69 7a 65 28 (y = [].resize(
0320: 78 2e 6c 65 6e 67 74 68 28 29 2d 79 2e 6c 65 6e x.length()-y.len
0330: 67 74 68 28 29 2c 30 29 2e 6d 65 72 67 65 28 79 gth(),0).merge(y
0340: 29 29 3b 0a 09 7a 20 3d 20 5b 5d 2e 72 65 73 69 ));..z = [].resi
0350: 7a 65 28 78 2e 6c 65 6e 67 74 68 28 29 2c 20 30 ze(x.length(), 0
0360: 29 3b 0a 09 69 20 3d 20 78 2e 6c 65 6e 67 74 68 );..i = x.length
0370: 28 29 2d 31 3b 0a 09 63 61 72 72 79 20 3d 20 30 ()-1;..carry = 0
0380: 3b 0a 09 6c 6f 6f 70 20 7b 0a 09 09 7a 5b 69 5d ;..loop {...z[i]
0390: 20 20 3d 20 78 5b 69 5d 20 2d 20 79 5b 69 5d 20 = x[i] - y[i]
03a0: 2d 20 63 61 72 72 79 3b 0a 09 09 63 61 72 72 79 - carry;...carry
03b0: 20 3d 20 7a 5b 69 5d 20 3c 20 30 20 3f 20 28 7a = z[i] < 0 ? (z
03c0: 5b 69 5d 3d 7a 5b 69 5d 2b 31 30 3b 20 31 29 20 [i]=z[i]+10; 1)
03d0: 3a 20 30 3b 0a 09 09 28 69 3d 69 2d 31 29 20 3c : 0;...(i=i-1) <
03e0: 20 30 20 3f 20 72 65 74 75 72 6e 3b 0a 09 7d 3b 0 ? return;..};
03f0: 0a 09 68 65 61 64 20 3d 20 30 3b 0a 09 6c 6f 6f ..head = 0;..loo
0400: 70 20 7b 0a 09 09 68 65 61 64 20 3d 3d 20 7a 2e p {...head == z.
0410: 6c 65 6e 67 74 68 28 29 2d 31 20 3f 20 72 65 74 length()-1 ? ret
0420: 75 72 6e 3b 0a 09 09 7a 5b 68 65 61 64 5d 20 21 urn;...z[head] !
0430: 3d 20 30 20 3f 20 72 65 74 75 72 6e 3b 0a 09 09 = 0 ? return;...
0440: 68 65 61 64 20 3d 20 68 65 61 64 20 2b 20 31 3b head = head + 1;
0450: 0a 09 7d 3b 0a 09 72 65 74 75 72 6e 20 7a 2e 73 ..};..return z.s
0460: 6c 69 63 65 28 68 65 61 64 2c 20 7a 2e 6c 65 6e lice(head, z.len
0470: 67 74 68 28 29 29 3b 0a 7d 3b 0a 0a 67 6c 6f 62 gth());.};..glob
0480: 61 6c 20 44 42 4c 20 3d 20 66 75 6e 63 20 7b 0a al DBL = func {.
0490: 09 61 72 67 20 78 3b 0a 0a 09 7a 20 3d 20 5b 5d .arg x;...z = []
04a0: 2e 72 65 73 69 7a 65 28 78 2e 6c 65 6e 67 74 68 .resize(x.length
04b0: 28 29 2c 20 30 29 3b 0a 09 69 20 3d 20 78 2e 6c (), 0);..i = x.l
04c0: 65 6e 67 74 68 28 29 2d 31 3b 0a 09 63 61 72 72 ength()-1;..carr
04d0: 79 20 3d 20 30 3b 0a 09 6c 6f 6f 70 20 7b 0a 09 y = 0;..loop {..
04e0: 09 7a 5b 69 5d 20 20 3d 20 78 5b 69 5d 20 2b 20 .z[i] = x[i] +
04f0: 78 5b 69 5d 20 2b 20 63 61 72 72 79 3b 0a 09 09 x[i] + carry;...
0500: 63 61 72 72 79 20 3d 20 7a 5b 69 5d 20 3e 20 39 carry = z[i] > 9
0510: 20 3f 20 28 7a 5b 69 5d 3d 7a 5b 69 5d 2d 31 30 ? (z[i]=z[i]-10
0520: 3b 20 31 29 20 3a 20 30 3b 0a 09 09 28 28 69 3d ; 1) : 0;...((i=
0530: 69 2d 31 29 20 3c 20 30 29 20 3f 20 72 65 74 75 i-1) < 0) ? retu
0540: 72 6e 3b 0a 09 7d 3b 0a 09 72 65 74 75 72 6e 20 rn;..};..return
0550: 28 63 61 72 72 79 3d 3d 31 20 3f 20 5b 31 5d 2e (carry==1 ? [1].
0560: 6d 65 72 67 65 28 7a 29 20 3a 20 7a 29 3b 0a 7d merge(z) : z);.}
0570: 3b 0a 0a 67 6c 6f 62 61 6c 20 44 49 46 20 3d 20 ;..global DIF =
0580: 66 75 6e 63 20 7b 0a 09 61 72 67 20 78 3b 0a 09 func {..arg x;..
0590: 61 72 67 20 79 3b 0a 09 72 65 74 75 72 6e 20 4c arg y;..return L
05a0: 45 53 53 28 78 2c 20 79 29 20 3f 20 53 55 42 28 ESS(x, y) ? SUB(
05b0: 79 2c 20 78 29 20 3a 20 53 55 42 28 78 2c 20 79 y, x) : SUB(x, y
05c0: 29 3b 0a 7d 3b 0a 0a 67 6c 6f 62 61 6c 20 4d 4f );.};..global MO
05d0: 44 20 3d 20 66 75 6e 63 20 7b 0a 09 61 72 67 20 D = func {..arg
05e0: 78 3b 0a 09 61 72 67 20 79 3b 0a 0a 09 4c 45 53 x;..arg y;...LES
05f0: 53 28 78 2c 79 29 20 3f 20 72 65 74 75 72 6e 20 S(x,y) ? return
0600: 78 3b 0a 09 7a 20 3d 20 4d 4f 44 28 78 2c 20 44 x;..z = MOD(x, D
0610: 42 4c 28 79 29 29 3b 0a 09 4c 45 53 53 28 7a 2c BL(y));..LESS(z,
0620: 79 29 20 3f 20 72 65 74 75 72 6e 20 7a 3b 0a 09 y) ? return z;..
0630: 72 65 74 75 72 6e 20 53 55 42 28 7a 2c 79 29 3b return SUB(z,y);
0640: 0a 7d 3b 0a 0a 67 6c 6f 62 61 6c 20 49 53 5a 45 .};..global ISZE
0650: 52 4f 20 3d 20 66 75 6e 63 20 7b 0a 09 61 72 67 RO = func {..arg
0660: 20 78 3b 0a 09 72 65 74 75 72 6e 20 78 5b 30 5d x;..return x[0]
0670: 20 3d 3d 20 30 3b 0a 7d 3b 0a 0a 67 6c 6f 62 61 == 0;.};..globa
0680: 6c 20 47 43 44 20 3d 20 66 75 6e 63 20 7b 0a 09 l GCD = func {..
0690: 61 72 67 20 78 3b 0a 09 61 72 67 20 79 3b 0a 09 arg x;..arg y;..
06a0: 72 65 74 75 72 6e 20 49 53 5a 45 52 4f 28 78 29 return ISZERO(x)
06b0: 20 3f 20 79 20 3a 20 47 43 44 28 4d 4f 44 28 79 ? y : GCD(MOD(y
06c0: 2c 78 29 2c 78 29 3b 0a 7d 3b 0a 0a 23 23 23 23 ,x),x);.};..####
06d0: 23 23 23 23 23 23 23 23 23 23 23 23 23 23 23 23 ################
06e0: 23 23 23 23 23 23 23 23 23 23 23 23 23 23 23 23 ################
06f0: 23 23 23 23 23 23 23 23 23 23 23 23 23 23 23 23 ################
0700: 23 23 23 23 23 23 23 23 23 23 23 23 23 23 23 23 ################
0710: 23 23 23 23 23 23 23 23 23 0a 0a 73 6f 6c 76 65 #########..solve
0720: 20 3d 20 66 75 6e 63 20 7b 0a 09 61 72 67 20 4e = func {..arg N
0730: 3b 0a 09 61 72 67 20 74 3b 0a 09 74 20 3d 20 74 ;..arg t;..t = t
0740: 2e 6d 61 70 28 20 66 75 6e 63 7b 72 65 74 75 72 .map( func{retur
0750: 6e 20 46 52 4f 4d 5f 53 54 52 49 4e 47 28 74 68 n FROM_STRING(th
0760: 69 73 29 3b 7d 20 29 3b 0a 0a 09 6c 65 78 69 63 is);} );...lexic
0770: 61 6c 20 74 30 20 3d 20 74 5b 30 5d 3b 0a 09 6c al t0 = t[0];..l
0780: 65 78 69 63 61 6c 20 67 20 20 3d 20 44 49 46 28 exical g = DIF(
0790: 74 30 2c 20 74 5b 31 5d 29 3b 0a 09 74 2e 73 6c t0, t[1]);..t.sl
07a0: 69 63 65 28 32 2c 20 74 2e 6c 65 6e 67 74 68 28 ice(2, t.length(
07b0: 29 29 2e 6d 61 70 28 66 75 6e 63 7b 0a 09 09 67 )).map(func{...g
07c0: 20 3d 20 47 43 44 28 67 2c 20 44 49 46 28 74 30 = GCD(g, DIF(t0
07d0: 2c 20 74 68 69 73 29 29 3b 0a 09 7d 29 3b 0a 09 , this));..});..
07e0: 72 20 3d 20 4d 4f 44 28 74 5b 30 5d 2c 20 67 29 r = MOD(t[0], g)
07f0: 3b 0a 09 72 65 74 75 72 6e 20 54 4f 5f 53 54 52 ;..return TO_STR
0800: 49 4e 47 28 20 49 53 5a 45 52 4f 28 72 29 20 3f ING( ISZERO(r) ?
0810: 20 72 20 3a 20 44 49 46 28 67 2c 72 29 20 29 3b r : DIF(g,r) );
0820: 0a 7d 3b 0a 0a 69 6e 70 75 74 20 3d 20 73 79 73 .};..input = sys
0830: 2e 6c 69 62 72 61 72 79 28 22 73 74 72 65 61 6d .library("stream
0840: 73 22 29 2e 73 74 64 69 6f 28 29 2e 72 65 61 64 s").stdio().read
0850: 28 31 30 30 30 30 30 30 30 30 30 29 2e 73 70 6c (1000000000).spl
0860: 69 74 28 22 5c 6e 22 29 2e 6d 61 70 28 66 75 6e it("\n").map(fun
0870: 63 7b 72 65 74 75 72 6e 20 74 68 69 73 2e 73 70 c{return this.sp
0880: 6c 69 74 28 22 20 22 29 3b 7d 29 3b 0a 43 20 3d lit(" ");});.C =
0890: 20 69 6e 70 75 74 5b 30 5d 5b 30 5d 2e 6e 75 6d input[0][0].num
08a0: 28 29 3b 0a 0a 43 61 73 65 49 44 20 3d 20 28 61 ();..CaseID = (a
08b0: 72 67 73 2e 6c 65 6e 67 74 68 28 29 20 3e 3d 20 rgs.length() >=
08c0: 32 20 3f 20 61 72 67 73 5b 31 5d 2e 6e 75 6d 28 2 ? args[1].num(
08d0: 29 20 3a 20 31 29 3b 0a 6c 6f 6f 70 20 7b 0a 09 ) : 1);.loop {..
08e0: 22 43 61 73 65 20 23 22 2e 70 72 69 6e 74 28 29 "Case #".print()
08f0: 3b 0a 09 43 61 73 65 49 44 2e 70 72 69 6e 74 28 ;..CaseID.print(
0900: 29 3b 0a 09 22 3a 20 22 2e 70 72 69 6e 74 28 29 );..": ".print()
0910: 3b 0a 09 73 6f 6c 76 65 28 20 69 6e 70 75 74 5b ;..solve( input[
0920: 43 61 73 65 49 44 5d 5b 30 5d 2e 6e 75 6d 28 29 CaseID][0].num()
0930: 2c 20 69 6e 70 75 74 5b 43 61 73 65 49 44 5d 2e , input[CaseID].
0940: 73 6c 69 63 65 28 31 2c 69 6e 70 75 74 5b 43 61 slice(1,input[Ca
0950: 73 65 49 44 5d 2e 6c 65 6e 67 74 68 28 29 29 20 seID].length())
0960: 29 2e 70 72 69 6e 74 28 29 3b 0a 09 22 5c 6e 22 ).print();.."\n"
0970: 2e 70 72 69 6e 74 28 29 3b 0a 09 28 28 43 61 73 .print();..((Cas
0980: 65 49 44 20 3d 20 43 61 73 65 49 44 2b 31 29 20 eID = CaseID+1)
0990: 3e 20 43 29 20 3f 20 72 65 74 75 72 6e 3b 0a 7d > C) ? return;.}
09a0: 3b 0a ;.