0
Your rating: None

CodeChef submission 84252 (C++ 4.0.0-8)

CodeChef submission 84252 (C++ 4.0.0-8) plaintext list. Status: AC, problem G1, contest SEP09. By gmark (Mark Greve), 2009-09-02 11:30:25.
  1. #include <algorithm>
  2. #include <cstdio>
  3. #include <cstring>
  4. using namespace std;
  5.  
  6. int precalc[21][601]={{0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0},{1,2,7,4,1,8,2,1,4,7,2,8,1,2,7,4,1,8,2,1,4,7,2,8,1,2,7,4,1,8,2,1,4,7,2,8,1,2,7,4,1,8,2,1,4,7,2,8,1,2,7,4,1,8,2,1,4,7,2,8,1,2,7,4,1,8,2,1,4,7,2,8,1,2,7,4,1,8,2,1,4,7,2,8,1,2,7,4,1,8,2,1,4,7,2,8,1,2,7,4,1,8,2,1,4,7,2,8,1,2,7,4,1,8,2,1,4,7,2,8,1,2,7,4,1,8,2,1,4,7,2,8,1,2,7,4,1,8,2,1,4,7,2,8,1,2,7,4,1,8,2,1,4,7,2,8,1,2,7,4,1,8,2,1,4,7,2,8,1,2,7,4,1,8,2,1,4,7,2,8,1,2,7,4,1,8,2,1,4,7,2,8,1,2,7,4,1,8,2,1,4,7,2,8,1,2,7,4,1,8,2,1,4,7,2,8,1,2,7,4,1,8,2,1,4,7,2,8,1,2,7,4,1,8,2,1,4,7,2,8,1,2,7,4,1,8,2,1,4,7,2,8,1,2,7,4,1,8,2,1,4,7,2,8,1,2,7,4,1,8,2,1,4,7,2,8,1,2,7,4,1,8,2,1,4,7,2,8,1,2,7,4,1,8,2,1,4,7,2,8,1,2,7,4,1,8,2,1,4,7,2,8,1,2,7,4,1,8,2,1,4,7,2,8,1,2,7,4,1,8,2,1,4,7,2,8,1,2,7,4,1,8,2,1,4,7,2,8,1,2,7,4,1,8,2,1,4,7,2,8,1,2,7,4,1,8,2,1,4,7,2,8,1,2,7,4,1,8,2,1,4,7,2,8,1,2,7,4,1,8,2,1,4,7,2,8,1,2,7,4,1,8,2,1,4,7,2,8,1,2,7,4,1,8,2,1,4,7,2,8,1,2,7,4,1,8,2,1,4,7,2,8,1,2,7,4,1,8,2,1,4,7,2,8,1,2,7,4,1,8,2,1,4,7,2,8,1,2,7,4,1,8,2,1,4,7,2,8,1,2,7,4,1,8,2,1,4,7,2,8,1,2,7,4,1,8,2,1,4,7,2,8,1,2,7,4,1,8,2,1,4,7,2,8,1,2,7,4,1,8,2,1,4,7,2,8,1,2,7,4,1,8,2,1,4,7,2,8,1,2,7,4,1,8,2,1,4,7,2,8,1,2,7,4,1,8,2,1,4,7,2,8,1,2,7,4,1,8,2,1,4,7,2,8,1,2,7,4,1,8,2,1,4,7,2,8,1,2,7,4,1,8,2,1,4,7,2,8,1,2,7,4,1,8,2,1,4,7,2,8,1},{41,99,10,143,14,173,87,31,8,103,140,127,55,1,41,32,49,133,136,29,138,31,73,155,47,103,173,32,169,1,177,25,142,1,41,99,10,143,41,103,20,119,8,160,69,153,108,1,41,32,87,56,136,29,138,92,73,50,16,103,173,32,41,1,170,25,14,1,41,99,10,143,16,103,140,118,22,1,140,153,142,177,28,1,127,25,136,32,138,31,73,160,16,103,173,32,8,1,165,25,118,1,41,31,10,166,79,25,41,118,22,1,14,146,71,70,32,31,55,121,133,103,138,31,112,160,16,141,140,160,41,1,165,25,167,60,8,31,10,166,79,25,162,148,22,1,140,25,142,38,28,31,49,137,26,25,8,31,112,97,16,141,140,160,8,148,140,25,77,38,158,31,10,166,18,25,155,148,8,1,14,164,146,38,28,31,157,56,26,144,138,31,118,137,16,25,146,7,8,66,148,25,77,38,47,62,10,99,47,133,155,148,8,125,55,155,146,38,28,31,108,38,26,144,138,31,118,50,150,25,81,101,41,66,148,147,77,123,47,56,10,99,16,133,112,148,8,125,55,54,146,38,41,31,108,38,51,133,138,31,73,50,150,5,146,153,41,34,148,25,26,123,47,62,10,136,104,133,16,148,8,125,16,25,143,7,28,31,108,38,26,132,49,31,136,50,150,140,135,143,41,34,148,56,14,58,49,62,10,38,104,133,16,148,8,130,10,25,143,7,110,31,108,70,26,88,49,31,136,29,16,70,146,38,41,34,148,56,14,27,49,62,108,136,104,88,16,32,8,130,55,25,47,7,110,34,8,84,26,76,49,31,22,50,148,140,16,142,104,66,128,32,14,88,49,62,8,136,104,88,16,142,8,1,118,25,47,38,132,62,87,32,26,36,49,31,22,29,16,48,128,143,77,66,128,32,14,47,12,121,8,136,104,133,16,135,8,1,10,25,14,38,132,36,128,92,73,133,16,31,22,1,16,48,106,143,122,66,43,32,14,27,49,121,8,136,22,133,49,135,28,1,10,128,47,38,56,11,73,38,104,32,16,135,136,29,10,1,106,82,110,131,43,32,14,27,49,121,8,32,22,125,49,135,14,130,10,128,47,38,83,36,55,38,136,32,12,135,8,29,1,48,128,82,130,131,43,32,14,16,22,109,55,32,104,99,49,15,47,131,10,128,47,32,81,36,55,38,114,32,49,78,8,131,95,48,128,82,69,123,43,32,41,125,49,109,14,32,104,99,16,91,47,104,10,129,128,38,81,36,55,32,114,127,49,7,8,131,130,129,128,50,16,123,128,32,41,25,26,121,14,32,75,99,118,91,104,31,10,109,99,38,81,36,73,1,114,99,49,109,8},{3,17,16,5,4,3,2,8,9,14,15,5,4,17,16,2,3,4,5,15,14,9,8,2,3,17,16,5,4,3,2,8,9,14,15,5,4,17,16,2,3,4,5,15,14,9,8,2,3,17,16,5,4,3,2,8,9,14,15,5,4,17,16,2,3,4,5,15,14,9,8,2,3,17,16,5,4,3,2,8,9,14,15,5,4,17,16,2,3,4,5,15,14,9,8,2,3,17,16,5,4,3,2,8,9,14,15,5,4,17,16,2,3,4,5,15,14,9,8,2,3,17,16,5,4,3,2,8,9,14,15,5,4,17,16,2,3,4,5,15,14,9,8,2,3,17,16,5,4,3,2,8,9,14,15,5,4,17,16,2,3,4,5,15,14,9,8,2,3,17,16,5,4,3,2,8,9,14,15,5,4,17,16,2,3,4,5,15,14,9,8,2,3,17,16,5,4,3,2,8,9,14,15,5,4,17,16,2,3,4,5,15,14,9,8,2,3,17,16,5,4,3,2,8,9,14,15,5,4,17,16,2,3,4,5,15,14,9,8,2,3,17,16,5,4,3,2,8,9,14,15,5,4,17,16,2,3,4,5,15,14,9,8,2,3,17,16,5,4,3,2,8,9,14,15,5,4,17,16,2,3,4,5,15,14,9,8,2,3,17,16,5,4,3,2,8,9,14,15,5,4,17,16,2,3,4,5,15,14,9,8,2,3,17,16,5,4,3,2,8,9,14,15,5,4,17,16,2,3,4,5,15,14,9,8,2,3,17,16,5,4,3,2,8,9,14,15,5,4,17,16,2,3,4,5,15,14,9,8,2,3,17,16,5,4,3,2,8,9,14,15,5,4,17,16,2,3,4,5,15,14,9,8,2,3,17,16,5,4,3,2,8,9,14,15,5,4,17,16,2,3,4,5,15,14,9,8,2,3,17,16,5,4,3,2,8,9,14,15,5,4,17,16,2,3,4,5,15,14,9,8,2,3,17,16,5,4,3,2,8,9,14,15,5,4,17,16,2,3,4,5,15,14,9,8,2,3,17,16,5,4,3,2,8,9,14,15,5,4,17,16,2,3,4,5,15,14,9,8,2,3,17,16,5,4,3,2,8,9,14,15,5,4,17,16,2,3,4,5,15,14,9,8,2,3,17,16,5,4,3,2,8,9,14,15,5,4,17,16,2,3,4,5,15,14,9,8,2,3,17,16,5,4,3,2,8,9,14,15,5,4,17,16,2,3,4,5,15,14,9,8,2,3,17,16,5,4,3,2,8,9,14,15,5,4,17,16,2,3,4,5,15,14,9,8,2,3,17,16,5,4,3,2,8,9,14,15,5,4,17,16,2,3,4,5,15,14,9,8,2,3},{92,100,25,12,5,22,31,85,61,59,12,92,5,40,119,107,39,120,16,40,25,5,53,64,23,46,16,12,50,64,5,22,25,85,59,50,92,5,22,83,33,90,50,16,12,119,107,40,52,22,46,85,59,40,50,5,64,30,33,126,73,50,59,16,31,22,92,10,59,16,25,83,64,40,126,98,92,70,59,16,12,64,31,53,107,16,108,33,5,12,31,16,92,46,59,85,50,16,31,40,12,92,128,5,126,50,12,107,73,39,92,25,85,50,12,70,23,98,119,64,12,40,5,46,22,52,39,85,25,12,5,73,39,59,109,64,16,100,33,50,5,22,73,92,85,119,50,40,107,12,10,120,33,16,50,12,107,22,61,46,73,64,25,12,50,5,128,107,46,85,64,119,12,50,90,92,85,25,52,50,109,12,39,31,107,46,59,73,33,5,64,120,39,12,85,25,5,109,46,16,61,64,107,92,85,128,90,82,39,3,16,12,100,59,5,90,31,12,39,50,25,52,5,22,59,12,31,39,64,16,25,113,82,46,22,64,16,39,92,12,5,46,109,73,52,50,16,78,64,39,22,52,10,85,16,109,100,50,5,22,64,128,16,109,12,50,64,39,10,92,85,16,3,12,128,22,73,46,59,16,92,12,39,90,83,52,46,10,25,50,120,12,23,22,73,25,64,85,50,12,39,128,64,109,61,10,5,50,46,22,39,52,85,10,16,128,59,46,31,10,39,16,25,5,128,73,22,64,3,16,59,50,5,70,22,46,126,52,16,59,107,73,31,46,10,85,64,40,59,39,5,22,61,3,64,39,12,50,70,46,22,79,64,109,25,12,98,120,83,46,85,92,16,59,120,128,5,108,100,118,25,85,59,40,39,31,70,10,64,16,85,73,12,31,126,119,107,25,50,12,16,59,5,39,10,25,16,107,64,12,98,85,40,16,93,5,50,59,64,39,52,73,25,50,12,46,22,113,39,10,16,33,50,46,5,12,107,85,70,16,25,50,83,23,61,46,16,10,70,12,64,50,22,61,119,52,134,126,107,73,83,12,128,85,16,59,40,12,5,22,92,79,85,16,12,59,39,23,70,61,25,16,85,50,40,73,5,12,92,85,16,59,40,12,5,98,52,118,85,107,64,5,59,98,12,16,92,64,5,50,12,22,85,40,61,25,12,128,82,31,5,39,40,107,64,50,22,5,59,39,119,16,92,73,33,12,22,79,85,73,25,50,46,107,31,119,70,10,92,16,2,64,22,5,100,61,59,25,64,73,12,50,52,5,25,85,10,12,40,107,128,71,33,92,16,107,98,59,83,5,61,85,119,73,107,113,52,50,12,46,25,10,59,40,128,31,12,109,64,16,5},{12,11,14,9,8,22,23,5,4,3,2,16,17,10,11,12,9,14,15,17,16,2,3,4,5,23,22,13,12,11,14,9,8,22,23,5,4,3,2,16,17,10,11,12,9,14,15,17,16,2,3,4,5,23,22,13,12,11,14,9,8,22,23,5,4,3,2,16,17,10,11,12,9,14,15,17,16,2,3,4,5,23,22,13,12,11,14,9,8,22,23,5,4,3,2,16,17,10,11,12,9,14,15,17,16,2,3,4,5,23,22,13,12,11,14,9,8,22,23,5,4,3,2,16,17,10,11,12,9,14,15,17,16,2,3,4,5,23,22,13,12,11,14,9,8,22,23,5,4,3,2,16,17,10,11,12,9,14,15,17,16,2,3,4,5,23,22,13,12,11,14,9,8,22,23,5,4,3,2,16,17,10,11,12,9,14,15,17,16,2,3,4,5,23,22,13,12,11,14,9,8,22,23,5,4,3,2,16,17,10,11,12,9,14,15,17,16,2,3,4,5,23,22,13,12,11,14,9,8,22,23,5,4,3,2,16,17,10,11,12,9,14,15,17,16,2,3,4,5,23,22,13,12,11,14,9,8,22,23,5,4,3,2,16,17,10,11,12,9,14,15,17,16,2,3,4,5,23,22,13,12,11,14,9,8,22,23,5,4,3,2,16,17,10,11,12,9,14,15,17,16,2,3,4,5,23,22,13,12,11,14,9,8,22,23,5,4,3,2,16,17,10,11,12,9,14,15,17,16,2,3,4,5,23,22,13,12,11,14,9,8,22,23,5,4,3,2,16,17,10,11,12,9,14,15,17,16,2,3,4,5,23,22,13,12,11,14,9,8,22,23,5,4,3,2,16,17,10,11,12,9,14,15,17,16,2,3,4,5,23,22,13,12,11,14,9,8,22,23,5,4,3,2,16,17,10,11,12,9,14,15,17,16,2,3,4,5,23,22,13,12,11,14,9,8,22,23,5,4,3,2,16,17,10,11,12,9,14,15,17,16,2,3,4,5,23,22,13,12,11,14,9,8,22,23,5,4,3,2,16,17,10,11,12,9,14,15,17,16,2,3,4,5,23,22,13,12,11,14,9,8,22,23,5,4,3,2,16,17,10,11,12,9,14,15,17,16,2,3,4,5,23,22,13,12,11,14,9,8,22,23,5,4,3,2,16,17,10,11,12,9,14,15,17,16,2,3,4,5,23,22,13,12,11,14,9,8,22,23,5,4,3,2,16,17,10,11,12,9,14,15,17,16,2,3,4,5,23,22,13,12,11,14,9,8,22,23,5,4,3,2,16,17,10,11,12,9,14,15,17,16,2,3,4,5,23,22,13,12,11,14,9,8,22,23,5,4,3,2,16,17},{713,564,566,643,463,302,357,574,320,665,650,468,501,411,447,451,728,630,580,507,458,120,368,59,356,202,428,585,377,349,307,72,599,195,597,460,297,542,537,711,252,166,700,480,16,517,713,690,197,626,511,609,120,269,62,134,650,589,431,399,560,657,242,645,438,406,593,570,543,704,671,652,309,444,600,560,663,38,195,388,340,556,386,281,666,282,455,221,617,288,534,17,562,156,610,421,283,672,527,570,711,604,447,441,443,380,564,567,647,626,592,336,391,556,254,296,164,176,415,645,362,498,73,583,123,434,391,325,699,557,162,451,650,409,393,259,305,227,564,597,400,403,338,282,149,655,239,667,518,377,16,451,616,184,594,583,390,371,321,11,162,253,650,670,263,413,288,672,646,663,644,489,611,439,543,205,251,682,442,395,565,258,551,230,658,625,615,437,352,555,253,651,644,363,393,112,512,514,599,230,16,610,357,59,520,249,234,623,202,426,484,544,646,560,227,297,391,327,656,639,542,252,586,222,399,431,546,209,544,643,459,457,60,321,358,650,254,148,430,483,426,288,518,224,657,579,614,339,327,355,250,219,498,396,502,503,377,331,518,211,458,582,640,541,537,553,218,603,65,362,560,22,544,242,633,143,478,282,557,553,204,223,201,584,617,500,366,583,562,580,578,494,30,543,320,539,183,235,450,604,424,532,560,225,242,614,608,136,460,538,251,203,239,147,328,268,350,550,194,155,108,608,508,374,557,554,239,626,85,585,16,365,351,197,194,580,387,90,568,262,555,251,134,602,603,561,53,519,565,593,230,597,520,340,492,40,629,218,618,251,98,514,448,583,579,172,141,542,402,422,613,162,221,393,303,33,382,544,259,224,195,154,554,17,543,316,217,162,586,84,85,379,52,562,139,137,579,386,423,543,538,222,90,221,513,517,452,567,214,193,598,594,460,355,462,302,251,134,163,408,444,567,549,565,170,174,122,539,434,541,236,237,131,177,103,377,445,546,544,567,171,541,537,506,434,296,176,558,586,580,328,51,500,70,195,193,340,104,520,524,507,130,202,128,233,349,514,587,518,37,226,225,541,525,216,13,204,586,183,251,147,329,99,242,544,228,73,577,521,536,556,203,167,553,112,514,442,333,550,214,140,126,479,510,477,541,46,223,575,251,517,97,329,529,214,224,90,525,93,12,205,420,251,84,147,512,289,465,550,209,228,432,326,341,539,78,555,559,557,528,112,100,364,544,362,212,224,228,463,538,476,521,569,148,219,513,399,377,288,409,261,563,224,520,509,340,524,130,167,233,348,66,431,208,22,199,212,538,16,72,540,357,248,557,219,517,183,377,380,512,244,170,536,92,524,386,202,266,31,356,150},{7,8,9,10,11,31,30,29,28,19,18,17,16,4,5,6,7,35,34,33,32,11,10,9,8,7,6,5,4,16,17,18,19,28,29,30,31,11,10,9,8,35,34,33,32,4,5,6,7,8,9,10,11,31,30,29,28,19,18,17,16,4,5,6,7,35,34,33,32,11,10,9,8,7,6,5,4,16,17,18,19,28,29,30,31,11,10,9,8,35,34,33,32,4,5,6,7,8,9,10,11,31,30,29,28,19,18,17,16,4,5,6,7,35,34,33,32,11,10,9,8,7,6,5,4,16,17,18,19,28,29,30,31,11,10,9,8,35,34,33,32,4,5,6,7,8,9,10,11,31,30,29,28,19,18,17,16,4,5,6,7,35,34,33,32,11,10,9,8,7,6,5,4,16,17,18,19,28,29,30,31,11,10,9,8,35,34,33,32,4,5,6,7,8,9,10,11,31,30,29,28,19,18,17,16,4,5,6,7,35,34,33,32,11,10,9,8,7,6,5,4,16,17,18,19,28,29,30,31,11,10,9,8,35,34,33,32,4,5,6,7,8,9,10,11,31,30,29,28,19,18,17,16,4,5,6,7,35,34,33,32,11,10,9,8,7,6,5,4,16,17,18,19,28,29,30,31,11,10,9,8,35,34,33,32,4,5,6,7,8,9,10,11,31,30,29,28,19,18,17,16,4,5,6,7,35,34,33,32,11,10,9,8,7,6,5,4,16,17,18,19,28,29,30,31,11,10,9,8,35,34,33,32,4,5,6,7,8,9,10,11,31,30,29,28,19,18,17,16,4,5,6,7,35,34,33,32,11,10,9,8,7,6,5,4,16,17,18,19,28,29,30,31,11,10,9,8,35,34,33,32,4,5,6,7,8,9,10,11,31,30,29,28,19,18,17,16,4,5,6,7,35,34,33,32,11,10,9,8,7,6,5,4,16,17,18,19,28,29,30,31,11,10,9,8,35,34,33,32,4,5,6,7,8,9,10,11,31,30,29,28,19,18,17,16,4,5,6,7,35,34,33,32,11,10,9,8,7,6,5,4,16,17,18,19,28,29,30,31,11,10,9,8,35,34,33,32,4,5,6,7,8,9,10,11,31,30,29,28,19,18,17,16,4,5,6,7,35,34,33,32,11,10,9,8,7,6,5,4,16,17,18,19,28,29,30,31,11,10,9,8,35,34,33,32,4,5,6,7,8,9,10,11,31,30,29,28,19,18,17,16,4,5,6,7,35,34,33,32,11,10,9,8,7,6,5,4,16,17,18,19,28,29,30,31,11,10,9,8,35,34,33,32,4,5,6,7,8,9,10,11,31,30,29,28,19,18,17,16,4,5,6,7,35,34,33,32,11,10,9,8},{10,26,181,102,66,64,269,212,4,7,130,144,257,77,79,241,240,224,180,157,143,142,285,6,7,4,146,212,236,62,79,225,224,143,51,49,140,243,201,122,21,6,4,61,185,92,79,256,9,142,83,225,182,164,122,51,5,47,128,92,93,296,272,256,142,102,100,10,81,181,65,64,7,5,4,147,122,187,258,62,8,9,24,34,83,64,290,308,21,236,147,146,7,187,63,92,26,27,10,140,164,242,51,105,20,7,237,236,45,296,274,214,27,25,218,224,165,9,32,105,123,147,20,130,236,214,197,92,117,27,224,201,159,35,142,286,64,78,23,104,168,185,237,196,117,92,25,27,141,32,181,201,83,106,7,239,236,212,45,170,215,79,26,157,159,218,201,143,105,104,107,128,20,46,44,197,212,272,259,241,240,157,166,164,33,83,4,20,239,171,170,199,45,257,227,226,164,156,34,216,284,105,81,22,65,21,62,199,257,213,103,93,26,241,33,203,218,271,20,236,237,128,46,198,257,212,143,142,101,159,93,201,122,33,32,107,128,144,130,46,47,9,8,101,103,142,164,35,167,7,284,122,107,171,169,63,215,147,11,9,227,142,167,48,202,64,271,5,131,147,129,47,44,63,20,212,180,142,143,165,103,51,121,105,185,7,45,61,171,197,118,293,93,92,274,242,32,33,34,122,46,236,81,7,83,214,117,256,119,240,48,51,21,217,218,120,267,238,131,66,197,47,143,79,256,182,10,94,200,48,20,104,82,238,65,129,47,26,146,102,262,256,117,183,180,33,50,34,122,67,83,6,212,199,26,100,92,119,117,164,141,183,51,200,266,268,120,65,123,6,238,25,26,27,32,48,35,201,200,105,82,80,67,168,47,46,296,198,256,241,180,156,78,104,141,35,65,122,80,47,46,44,26,237,102,78,77,6,4,32,35,34,143,123,83,27,198,184,61,257,237,239,182,158,157,6,143,201,282,271,82,184,169,61,145,46,166,101,93,165,33,77,182,202,122,104,64,80,10,45,236,199,198,277,213,93,103,156,35,201,243,285,80,83,147,61,65,9,255,256,103,100,93,5,34,35,6,242,285,284,237,171,170,273,145,102,94,292,167,35,164,200,241,258,64,257,170,144,63,45,8,46,102,255,227,95,6,50,201,48,257,256,60,169,27,45,212,146,78,102,100,181,166,50,141,203,184,105,82,66,81,170,144,129,182,140,92,33,166,35,240,203,64,200,83,184,170,60,147,146,213,78,102,103,92,164,20,201,143,227,170,130,46,47,215,145,105,256,201,92,143,102,7,33,158,241,186,44,120,106,47,213,212,130,167,143,22,33,51,240,200,122,65,64,67,128,105,45,61,257,256},{727,1135,27,1161,1122,1065,870,860,491,363,648,1035,1090,809,775,308,675,1104,1042,628,564,376,919,1053,344,1049,863,758,953,1134,1091,1090,1077,141,1061,325,262,388,258,745,428,333,367,213,1055,737,679,891,370,1104,498,336,94,1135,1140,967,51,447,712,1073,1026,332,676,675,324,77,772,105,1044,1113,659,751,816,1054,1052,446,350,346,394,755,1068,400,502,708,1092,1024,1091,570,325,1080,491,488,383,428,566,453,637,632,1066,629,940,1042,661,437,436,272,608,688,51,616,651,621,329,175,161,160,1075,264,750,860,746,298,633,1042,147,102,350,348,20,285,649,241,944,954,815,763,230,1091,707,299,1038,426,733,193,494,330,328,933,294,1049,1040,501,1025,499,279,275,272,762,603,1035,476,619,447,1038,1078,737,1024,417,1026,225,79,175,487,1066,1085,1068,886,101,732,695,285,244,247,243,596,598,646,469,411,1024,902,869,1039,1066,225,4,162,672,1060,46,105,501,1024,1057,1049,765,339,348,718,209,600,557,473,242,1038,1039,1027,1025,1024,432,487,660,237,75,393,1050,782,1038,928,1037,1044,66,179,1042,240,1030,794,316,1027,1026,977,1024,55,885,834,664,679,673,67,229,860,847,207,107,1024,706,185,704,25,536,719,408,22,691,246,894,990,274,1024,418,578,480,259,967,684,744,199,882,133,295,758,21,753,695,42,312,433,222,1017,72,467,369,368,919,52,112,679,591,230,671,790,63,42,643,816,142,29,32,801,704,605,555,281,788,185,176,541,216,212,920,432,720,632,579,748,51,846,119,133,131,34,515,85,973,605,108,64,966,810,777,700,79,216,159,220,208,886,665,989,666,23,923,906,890,138,194,88,30,967,92,304,713,604,649,607,102,988,987,862,415,628,858,983,272,502,939,917,513,912,508,791,297,87,80,202,614,935,108,551,646,641,943,72,13,621,574,49,673,65,64,58,61,57,874,342,289,340,944,293,702,91,96,766,717,666,428,265,65,927,59,369,921,781,564,144,252,254,189,25,569,441,302,442,21,652,614,122,643,141,611,168,326,263,79,232,774,915,488,68,212,679,283,246,908,20,863,392,777,711,642,512,708,134,235,622,166,493,806,65,789,909,370,421,311,9,147,119,661,189,313,818,280,176,82,240,22,17,141,545,419,256,557,322,175,73,834,267,328,431,491,412,346,245,560,179,240,890,779,432,342,609,254,881,815,882,902,800,205,228,163,7,261,878,779,721,828,824,13,833,818,817,769,667,177,7,788,689,584,498,547,877,382,417,858,549,170,169,335,333,494,449,655,5,564,603,828,569,349,187,186,95,342,341,863,700,833,731,315,849,54,59,7,134,320,486,74,844,631,833,781,185,568,786,444,753,606,508,245,177,600,498,613,311,31,400,73,24,515,239,205,493},{297,1026,261,260,1165,1163,6,225,434,247,1035,669,1204,1152,964,490,681,1175,239,1045,640,1160,149,1163,343,838,224,834,1108,581,856,291,764,223,33,54,604,131,1129,123,948,319,759,1137,159,800,1171,1080,153,821,557,1154,16,234,1153,343,711,897,1163,321,1120,1013,1106,271,1065,718,308,309,1152,1130,238,647,234,709,452,280,1034,1035,757,995,224,1044,478,1068,988,745,898,498,934,722,134,247,1122,757,1120,67,1092,698,1071,406,776,472,615,1082,1081,1080,408,1047,932,1072,1115,935,197,195,509,321,599,384,6,684,1122,1068,1103,641,642,1097,149,274,150,1027,927,1082,1044,1080,443,282,612,1121,174,661,1068,380,131,1062,1060,165,164,225,329,796,531,728,174,1025,765,187,186,1053,274,177,151,148,149,742,406,227,226,387,257,140,141,260,172,863,642,114,365,1096,367,634,178,1120,224,919,1087,319,1081,152,316,614,174,1054,556,1053,434,586,131,164,160,385,225,291,1025,978,1108,1039,767,1022,973,661,662,723,614,1100,454,499,544,331,648,578,1092,1070,291,136,137,170,397,789,258,87,297,482,756,676,871,533,65,649,696,1073,343,188,1050,316,322,520,1061,1060,382,1043,1042,128,167,122,848,1064,475,828,1032,1025,720,598,383,219,145,1074,148,1060,1044,502,1047,512,717,702,615,1054,261,342,270,708,317,379,288,167,634,165,1036,1025,364,25,1026,792,607,103,54,186,1063,67,66,1054,1043,1058,1040,260,165,121,671,14,744,7,290,422,343,296,86,538,537,481,365,694,224,514,59,760,412,547,544,321,525,32,1050,1044,552,661,679,329,64,161,728,1027,1026,838,765,565,699,1035,510,412,367,408,272,676,385,946,149,1025,1024,309,1040,518,474,680,797,1033,174,488,232,122,572,297,1026,1025,1024,60,149,777,834,255,64,612,184,233,175,17,86,552,1009,660,743,805,330,814,205,420,131,700,1024,994,765,156,911,187,16,677,695,694,59,62,311,450,1019,519,219,981,1013,744,987,474,479,853,757,573,554,1004,420,1002,593,128,700,723,254,547,998,994,589,101,905,208,975,952,245,919,227,130,981,979,978,420,697,504,84,136,974,776,490,553,695,644,572,967,52,176,76,150,680,700,234,588,172,341,175,779,799,742,164,694,289,228,131,290,129,764,765,966,254,924,311,536,404,575,678,672,738,951,151,146,914,165,681,377,546,744,39,940,33,136,936,247,246,197,934,933,92,329,804,409,357,100,413,906,904,812,173,649,554,301,416,913,879,290,165,150,390,116,895,112,906,378,905,730,156,64,53,404,814,859,878,900,776,503,164,567,290,545,184,908,634,136,692,169,122,881,244,879,624,464,566,565,149,310,254,67,66,865,814,100,437,340,33,778,876,847,834,128,874,613,15,255,261,200,812,623,159,376,758,331,357,329,76,280,16},{32,4,5,6,7,8,9,10,11,47,46,45,44,27,26,25,24,23,22,29,28,19,18,17,16,44,45,46,47,11,10,9,8,7,6,5,4,32,33,34,35,20,21,22,23,24,25,18,19,28,29,30,31,35,34,33,32,4,5,6,7,8,9,10,11,47,46,45,44,27,26,25,24,23,22,29,28,19,18,17,16,44,45,46,47,11,10,9,8,7,6,5,4,32,33,34,35,20,21,22,23,24,25,18,19,28,29,30,31,35,34,33,32,4,5,6,7,8,9,10,11,47,46,45,44,27,26,25,24,23,22,29,28,19,18,17,16,44,45,46,47,11,10,9,8,7,6,5,4,32,33,34,35,20,21,22,23,24,25,18,19,28,29,30,31,35,34,33,32,4,5,6,7,8,9,10,11,47,46,45,44,27,26,25,24,23,22,29,28,19,18,17,16,44,45,46,47,11,10,9,8,7,6,5,4,32,33,34,35,20,21,22,23,24,25,18,19,28,29,30,31,35,34,33,32,4,5,6,7,8,9,10,11,47,46,45,44,27,26,25,24,23,22,29,28,19,18,17,16,44,45,46,47,11,10,9,8,7,6,5,4,32,33,34,35,20,21,22,23,24,25,18,19,28,29,30,31,35,34,33,32,4,5,6,7,8,9,10,11,47,46,45,44,27,26,25,24,23,22,29,28,19,18,17,16,44,45,46,47,11,10,9,8,7,6,5,4,32,33,34,35,20,21,22,23,24,25,18,19,28,29,30,31,35,34,33,32,4,5,6,7,8,9,10,11,47,46,45,44,27,26,25,24,23,22,29,28,19,18,17,16,44,45,46,47,11,10,9,8,7,6,5,4,32,33,34,35,20,21,22,23,24,25,18,19,28,29,30,31,35,34,33,32,4,5,6,7,8,9,10,11,47,46,45,44,27,26,25,24,23,22,29,28,19,18,17,16,44,45,46,47,11,10,9,8,7,6,5,4,32,33,34,35,20,21,22,23,24,25,18,19,28,29,30,31,35,34,33,32,4,5,6,7,8,9,10,11,47,46,45,44,27,26,25,24,23,22,29,28,19,18,17,16,44,45,46,47,11,10,9,8,7,6,5,4,32,33,34,35,20,21,22,23,24,25,18,19,28,29,30,31,35,34,33,32,4,5,6,7,8,9,10,11,47,46,45,44,27,26,25,24,23,22,29,28,19,18,17,16,44,45,46,47,11,10,9,8,7,6,5,4,32,33,34,35,20,21,22,23,24,25,18,19,28,29,30,31,35,34,33,32,4,5,6,7,8,9,10,11,47,46,45,44,27,26,25,24,23,22,29,28,19,18,17,16,44,45,46,47,11,10,9,8,7,6,5,4,32,33,34,35},{136,340,1348,549,893,486,453,480,1354,568,1352,534,185,1365,1123,867,866,837,832,504,1078,167,496,471,309,617,616,1133,1132,1356,382,1354,1353,1318,299,492,433,370,1347,46,538,1344,185,832,1114,1306,273,272,466,509,1337,1110,479,418,1136,1137,1303,401,1324,1325,1322,1061,1208,288,485,480,481,1280,1336,1313,1312,1123,1285,592,1301,1328,1298,282,1046,427,426,578,394,585,1305,1276,1097,415,408,436,1316,201,439,462,269,407,1295,457,773,1320,993,394,392,399,362,1304,499,423,1187,1280,477,419,1303,1296,1236,1266,695,1038,1291,1290,230,1292,1294,1012,1259,1282,150,1108,1061,459,255,1067,358,1065,1072,212,419,1161,1271,1292,392,1272,1273,1265,1246,1286,1152,1284,375,233,267,1280,462,1033,1253,740,487,1231,1230,1043,397,247,500,1090,543,540,1273,128,1269,759,1255,1110,1111,1266,1097,470,414,415,230,701,203,1204,1205,1256,1255,1254,1216,219,252,149,248,1248,1128,1246,242,424,1145,499,766,733,1185,1184,1237,1094,403,180,200,167,166,1218,1213,1212,190,188,34,171,1227,1175,304,1224,1095,1171,1156,317,325,148,76,1216,757,1179,1178,1214,1166,1167,1076,1204,1078,440,666,1200,1037,1175,490,737,489,327,326,418,1082,1179,425,1133,1187,1186,76,1184,1074,1073,30,554,1078,281,1076,1067,723,205,413,124,1182,1177,1176,1059,1058,242,684,1060,1035,326,376,255,223,100,102,1167,97,1118,1145,1144,1162,1112,1156,604,191,752,729,728,119,852,1168,81,84,87,573,1163,1178,537,1176,543,1060,716,242,602,651,1153,362,1159,735,112,833,1110,1160,520,207,888,195,85,122,5,587,885,1058,1157,113,449,1142,1092,57,58,219,709,626,1163,1162,647,1160,840,47,844,41,442,380,1108,1152,621,578,93,1138,1139,1140,613,318,561,1130,139,137,48,28,1125,1126,191,74,260,1120,652,1108,885,628,576,741,1128,1114,1077,1112,192,121,584,585,364,806,1092,1093,1094,133,58,1090,1054,28,419,417,425,603,1116,294,15,731,1072,817,409,193,1024,1107,1054,1080,87,608,582,1033,1032,1099,1098,622,1044,1095,617,1041,1040,1078,419,682,1088,384,1048,107,1086,792,405,1083,1082,780,1080,1041,443,230,408,191,700,589,1072,501,1070,1069,218,1067,352,223,742,213,1062,211,174,1047,1030,224,1056,351,227,1035,1040,700,401,1039,1052,1051,1050,198,194,1017,1028,329,143,142,139,1041,397,537,1038,1037,542,1035,1002,1003,270,1001,1030,639,186,187,741,892,1024,1019,1018,175,585,983,883,1020,161,1011,131,166,1004,387,1006,1001,263,570,1002,428,996,221,485,484,994,977,291,490,201,402,947,944,280,894,415,312,988,501,500,136,994,464,425,956,957,384,969,968,271,149,148,948,975,634,184,187,947,946,920,964,967,980,309,610,977,976,384,932,557,420,929,970,476,946,496,211,965,806,453,962,961,960,924,488,922,921,920,299,827,917,916,405,914,585,912,136,939,818,141,687,943,16},{443,235,1054,1091,294,1089,835,291,1044,677,532,1082,33,346,347,385,375,371,246,1114,1108,862,70,1145,1161,659,1032,352,53,333,332,233,1157,120,1090,864,1130,1074,1075,683,628,289,47,42,375,243,1146,351,1139,1112,622,621,620,610,311,1030,967,408,326,324,320,363,231,1128,1096,1095,1094,1073,594,681,680,1050,300,377,39,379,372,373,418,582,1036,588,692,574,622,585,277,1027,438,332,325,207,92,998,1092,1094,1099,684,639,675,674,673,417,383,15,342,253,340,1072,1138,772,610,621,612,580,622,1033,1032,60,20,414,229,332,334,404,1097,1092,1095,1094,672,1090,1049,794,246,46,213,344,298,1075,391,941,384,581,1109,1107,586,1058,1025,1024,352,286,324,327,410,918,792,482,1092,686,675,1049,955,82,1040,346,383,341,336,243,1111,1109,1107,591,939,1104,943,1032,1025,1024,352,365,63,327,324,446,414,1093,1090,879,596,1073,652,215,1055,341,340,372,373,378,377,416,502,497,496,1110,589,667,1024,1037,1036,1034,329,207,232,361,913,438,454,675,677,1089,1074,1049,1040,1042,545,223,340,372,337,581,398,475,474,468,477,1038,938,772,574,238,811,320,335,442,274,314,313,456,42,481,640,1039,1055,39,213,1083,890,726,510,299,302,291,469,496,466,615,1056,811,228,574,236,540,711,739,433,409,184,157,151,921,488,1017,825,14,755,727,577,379,336,338,375,262,259,472,467,49,1034,1033,29,1025,562,364,712,707,326,459,36,283,451,455,448,1080,1078,1040,516,211,524,373,371,370,299,265,467,466,234,776,506,1006,1039,1024,575,540,542,775,742,1056,451,449,149,190,457,486,521,825,826,556,1052,1051,755,734,1048,470,128,288,133,24,475,1025,1024,1038,1037,1036,529,751,705,1032,188,273,149,277,176,449,793,1024,38,796,816,958,731,733,379,351,294,131,20,504,503,998,775,771,770,543,542,742,560,740,746,482,272,155,46,8,784,11,824,761,729,524,555,725,924,497,293,143,142,264,16,903,1029,860,965,962,1025,1024,560,704,74,189,79,177,176,280,13,40,39,793,578,720,548,551,733,293,260,165,48,17,496,899,830,389,774,24,562,104,574,1014,889,181,285,184,4,274,483,282,44,522,520,94,526,524,759,936,113,270,293,136,61,479,288,48,417,392,992,778,736,740,482,144,189,180,491,278,962,332,977,620,443,972,514,550,117,968,810,508,165,164,134,470,478,962,957,416,902,944,938,915,883,181,147,33,462,286,306,448,482,440,446,924,727,700,127,761,112,875,116,903,299,290,562,374,421,629,429,417,770,709,101,736,848,177,155,860,916,697,231,224,433,413,406,415,403,909,143,142,898,135,132,470,303,399,397,289,391,248,389,388,385,100,848,189,878,660,619,487,328,367,327,206,403,405,869,867,843,115,834,169,168,535,468,250},{433,476,1098,834,1082,1131,815,838,1024,265,353,251,1344,1314,841,1033,124,1304,480,1300,344,1299,587,1119,508,77,316,1243,1245,795,784,446,166,444,1282,163,1280,1089,1226,1224,1156,261,425,1099,1219,482,1134,249,1111,460,1301,253,216,1207,1104,1241,468,306,465,408,1084,9,1086,1313,1312,1289,1288,173,867,1279,254,83,390,388,387,61,1120,1033,1214,1113,1114,243,1303,241,214,1145,1299,746,401,1296,476,314,440,742,464,1288,345,814,1217,1216,636,1280,1221,321,1007,245,1154,425,268,1167,1028,267,1108,1107,1106,151,1104,717,1118,718,194,1115,1114,1113,1282,1281,1280,473,1268,902,1266,1264,1104,1127,293,658,1036,1217,1098,1087,323,1256,1150,1075,1074,153,190,1079,831,282,316,522,1106,1109,1110,1087,72,195,194,197,539,667,1247,533,670,352,1076,422,1122,1217,688,242,727,1087,1084,1085,254,31,1080,1246,226,311,1176,1179,1180,169,351,71,204,205,202,1165,200,161,626,597,1028,1029,1216,594,1196,1225,1134,1223,1215,157,1074,153,16,1079,1190,237,286,282,710,1110,128,1200,193,169,228,1164,224,137,136,1025,602,1191,495,1188,1186,631,320,21,1176,328,1084,1085,1082,360,1080,785,336,1117,138,35,168,143,1072,71,128,1153,164,1093,1036,41,1038,484,1122,625,592,426,156,1167,1134,113,112,221,218,1077,1040,151,556,1105,1106,1081,576,554,128,686,1112,1057,680,171,36,173,38,1025,1062,1065,574,1067,248,390,806,1071,1070,127,186,243,94,215,1080,1119,1024,1105,1104,617,6,432,1152,525,70,69,44,1128,1066,65,562,774,16,155,636,187,318,159,302,113,84,145,146,219,1106,151,1104,1039,719,413,441,1115,1114,1113,514,513,400,71,1028,836,1026,606,118,452,58,361,146,25,182,888,88,686,1112,1113,265,93,54,1079,586,623,401,613,514,338,435,145,1120,195,226,308,76,1067,1064,1102,1088,1025,1024,320,240,185,213,63,84,27,60,29,148,151,1054,521,608,1041,1040,1043,1044,507,48,232,44,101,202,65,1026,483,1024,151,1036,1037,146,1035,1032,702,562,49,90,21,1044,1043,1018,880,160,743,162,165,164,739,46,47,192,143,34,1081,36,39,38,1025,734,19,795,1069,574,1067,448,1065,1064,1049,483,149,1052,151,150,1055,613,139,520,309,308,862,1046,207,1032,45,130,43,1036,41,1038,722,1024,261,1026,364,1028,564,142,1031,1046,1045,989,1043,1042,523,1040,337,132,682,319,167,46,205,32,1031,1030,786,906,227,174,225,1024,420,385,267,1021,569,998,996,997,1016,1015,884,240,1012,546,1010,403,676,344,35,548,990,991,423,799,11,961,960,997,957,908,153,910,992,979,157,487,974,975,990,24,988,987,796,927,926,925,447,132,13,773,317,961,498,508,73,973,972,971,970,944,838,695,600,326,29,60,904,961,960,246,936,20,21,18,256,120,914,679,916,917,918,340,947,946,183,944,908,909,910,911,896,897,898,899},{16,71,70,69,68,67,66,65,64,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,63,62,61,60,59,58,57,56,39,38,37,36,35,34,33,32,8,9,10,11,12,13,14,15,71,70,69,68,67,66,65,64,23,22,21,20,19,18,17,16,15,14,13,12,11,10,9,8,32,33,34,35,36,37,38,39,56,57,58,59,60,61,62,63,23,22,21,20,19,18,17,16,71,70,69,68,67,66,65,64,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,63,62,61,60,59,58,57,56,39,38,37,36,35,34,33,32,8,9,10,11,12,13,14,15,71,70,69,68,67,66,65,64,23,22,21,20,19,18,17,16,15,14,13,12,11,10,9,8,32,33,34,35,36,37,38,39,56,57,58,59,60,61,62,63,23,22,21,20,19,18,17,16,71,70,69,68,67,66,65,64,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,63,62,61,60,59,58,57,56,39,38,37,36,35,34,33,32,8,9,10,11,12,13,14,15,71,70,69,68,67,66,65,64,23,22,21,20,19,18,17,16,15,14,13,12,11,10,9,8,32,33,34,35,36,37,38,39,56,57,58,59,60,61,62,63,23,22,21,20,19,18,17,16,71,70,69,68,67,66,65,64,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,63,62,61,60,59,58,57,56,39,38,37,36,35,34,33,32,8,9,10,11,12,13,14,15,71,70,69,68,67,66,65,64,23,22,21,20,19,18,17,16,15,14,13,12,11,10,9,8,32,33,34,35,36,37,38,39,56,57,58,59,60,61,62,63,23,22,21,20,19,18,17,16,71,70,69,68,67,66,65,64,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,63,62,61,60,59,58,57,56,39,38,37,36,35,34,33,32,8,9,10,11,12,13,14,15,71,70,69,68,67,66,65,64,23,22,21,20,19,18,17,16,15,14,13,12,11,10,9,8,32,33,34,35,36,37,38,39,56,57,58,59,60,61,62,63,23,22,21,20,19,18,17,16,71,70,69,68,67,66,65,64,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,63,62,61,60,59,58,57,56,39,38,37,36,35,34,33,32,8,9,10,11,12,13,14,15,71,70,69,68,67,66,65,64,23,22,21,20,19,18,17,16,15,14,13,12,11,10,9,8,32,33,34,35,36,37,38,39,56,57,58,59,60,61,62,63,23,22,21,20,19,18,17,16,71,70,69,68,67,66,65,64,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23},{65,212,209,1111,820,1128,969,655,373,1056,1031,1030,203,43,187,153,152,428,543,743,232,1072,1073,1074,1075,690,100,17,68,21,290,1129,403,240,259,1108,763,1027,1024,1031,1030,742,572,568,574,124,706,152,680,395,159,505,1088,1072,429,730,659,695,1077,261,260,163,130,132,128,50,763,545,1058,1024,1057,707,686,191,189,188,95,92,631,41,235,43,207,360,736,430,1050,789,477,167,161,102,65,64,23,71,135,1032,651,1060,121,623,1029,433,687,431,430,191,234,206,201,186,318,319,541,568,591,1083,656,1081,1080,1074,407,102,295,294,289,17,246,215,256,551,685,338,680,368,485,484,650,236,191,91,156,232,312,285,1045,1044,1043,787,657,628,618,201,789,19,210,55,208,247,243,1030,1029,550,1027,1025,945,655,652,122,47,186,127,126,125,317,95,55,429,362,809,509,205,859,858,663,547,21,20,160,262,164,67,66,1024,585,433,685,591,973,126,122,154,374,204,41,708,705,1058,430,935,1050,1051,1052,1053,1072,733,729,101,100,294,257,241,98,67,242,337,624,687,685,652,17,650,651,398,123,189,394,317,707,506,1048,1047,1046,1045,1044,689,102,98,97,16,17,256,289,247,161,546,294,374,337,336,370,1025,1024,631,569,71,542,46,315,314,650,65,1045,1044,589,206,333,1002,663,662,895,48,51,295,293,128,208,517,339,1028,212,482,916,1024,680,595,591,284,236,539,399,44,317,709,575,40,705,707,476,767,18,16,17,258,165,103,98,99,96,400,403,346,342,681,1011,1029,1008,952,741,284,1024,1019,120,205,705,329,328,367,991,619,191,616,362,65,133,589,68,242,97,23,215,211,865,18,407,923,682,655,686,159,158,14,88,155,312,123,1010,1008,890,69,68,1000,694,910,979,691,433,18,17,16,295,407,804,999,959,403,166,866,864,871,869,93,158,89,319,485,430,399,682,706,202,203,234,977,932,784,766,935,963,931,548,550,165,815,244,813,402,241,448,257,680,343,342,572,570,319,206,569,394,202,154,157,158,818,396,817,822,499,767,937,161,405,64,294,211,259,293,617,870,338,868,42,925,923,654,653,202,200,158,159,204,207,153,542,588,396,897,928,898,907,70,752,904,834,208,515,513,48,342,295,338,339,813,337,811,808,740,454,680,158,41,206,122,205,284,906,904,617,335,330,694,898,733,708,897,763,259,435,375,781,406,261,70,402,594,813,682,481,654,343,342,341,894,185,892,739,891,848,741,740,479,335,819,816,166,165,164,97,70,517,835,372,210,872,686,597,684,685,592,683,866,795,865,653,285,186,187,849,365,91,159,158,312,95,102,857,856,661,514,258,21,256,842,18,17,260,837,652,338,810,650,43,704,543,818,785,791,153,592,593,620,821,431,792,334,568,209,591,263,760},{219,1706,1704,140,1580,1581,1626,1700,660,1698,950,821,1695,1694,1693,277,1623,1690,1689,1665,405,1686,1141,928,45,1076,967,1002,905,1241,1677,901,121,120,127,126,1561,899,1562,1019,1218,1220,918,1664,1225,1161,1227,1169,716,197,169,69,64,378,137,434,1180,967,1590,928,1211,729,1143,1575,1574,530,221,393,1617,638,126,251,1652,1257,1127,1566,1121,1120,348,1133,100,750,227,106,66,170,169,1639,173,1634,1633,1632,1109,1108,267,638,1237,1232,251,126,89,88,17,1032,19,1621,1584,1619,22,1591,144,1190,1573,651,1608,578,1596,100,1288,1607,1606,1605,1538,1201,1087,1140,603,1081,600,251,756,55,120,50,126,48,1065,639,1465,1464,535,689,1321,748,41,1228,518,798,193,274,195,1316,1585,1055,1113,1183,1581,1040,560,365,146,779,91,1572,150,17,16,1032,20,21,1098,1566,1121,1564,1057,1193,642,227,68,1354,1284,346,1555,171,1553,1552,1551,1550,1549,1548,760,614,248,693,253,722,88,600,636,1538,1537,1536,1030,124,20,787,23,16,655,577,71,67,68,12,1524,1523,1522,1136,103,1050,1051,1412,1085,845,1512,92,766,218,604,1508,1307,144,1506,1505,530,178,1502,527,124,1499,1498,474,42,41,40,199,1492,69,1170,1489,1488,1487,972,973,1178,1483,963,151,1109,1479,1478,596,1157,145,1474,1306,1472,1471,1026,483,1468,645,1259,511,195,193,196,876,138,1459,1458,1148,1412,1276,1075,897,1076,908,1450,911,1271,243,53,52,1334,1443,954,18,1440,1439,1438,151,1095,1090,859,1433,225,69,68,64,70,1247,1325,142,1327,1423,1051,1237,905,1402,1403,660,326,221,1407,1413,168,1308,91,1310,1408,1120,1015,1250,952,1071,1020,915,1389,893,477,199,198,1407,41,678,1326,1403,1367,1401,1400,969,968,963,970,454,392,222,1392,1391,1390,92,1036,1110,979,1100,977,510,1023,1229,1228,1166,609,504,505,1285,64,1283,1372,1281,1316,1080,997,1006,823,1307,1186,1185,1141,1361,806,1359,455,1299,395,1355,1341,392,1067,1231,1350,1349,790,859,1313,1312,1344,852,553,102,1240,1247,1111,1110,842,841,909,835,355,354,10,495,1171,296,1228,303,300,88,434,50,1038,48,1209,1208,890,892,819,608,1134,1321,308,376,1318,349,1080,936,1295,1077,1312,1311,1310,933,1308,1186,334,269,325,125,357,303,301,299,1031,1035,1103,377,1032,510,1292,1291,1170,500,345,1287,305,1285,1284,1283,1104,1046,1280,1242,1246,1146,352,269,485,296,1137,1136,250,55,1274,1062,1272,1122,1270,1124,1127,1126,228,1256,406,100,340,1209,1210,452,1114,397,1240,1042,964,976,1041,358,1109,220,94,489,248,251,250,1230,1171,1170,429,1088,1100,1223,1188,1190,509,508,68,67,1208,1079,1202,348,344,972,1072,1141,389,390,1166,1137,1165,1061,251,127,182,183,266,176,268,1216,1180,1092,412,19,99,1034,1032,1033,10,194,1204,302,1170,511,1161,317,1049,1162,436,1055,438,429,427,1156,735,424,732,92,1065,144,452,1185,1129,1128,181,55,1062,1060,680,1058,404,230,98},{1320,132,1313,1164,1217,1166,1167,724,633,643,640,435,191,432,532,400,401,405,338,752,293,88,52,92,1288,1289,1292,1282,1245,1211,1210,1212,132,1203,1118,522,1222,1220,562,486,233,20,126,438,23,123,289,187,186,185,184,154,155,1026,1029,554,55,54,641,1069,1161,1142,1138,160,161,1144,637,335,632,1266,1257,93,1290,1274,1248,755,745,563,158,20,1194,16,211,191,49,608,205,825,365,363,553,93,11,10,9,13,131,262,295,294,484,330,560,1083,1082,841,1044,1087,1153,439,368,205,400,401,609,608,184,245,122,1167,1059,294,887,747,641,553,716,642,166,9,632,97,675,103,88,1211,334,1214,602,234,238,1216,720,604,670,610,434,1025,750,123,184,1115,745,717,697,242,243,642,483,258,206,207,160,131,200,1144,164,233,15,9,10,11,1142,964,287,286,667,664,437,154,153,191,435,18,749,67,47,44,698,646,553,132,130,632,261,424,558,9,1051,1049,1048,15,772,530,507,506,504,52,510,509,567,481,154,188,156,157,1176,1174,1069,1068,1065,1122,396,751,556,557,47,643,167,131,994,450,508,448,531,479,1191,1189,842,1100,759,400,313,1095,669,581,671,670,233,127,1038,1026,1027,1173,1172,1168,849,848,520,165,677,392,100,1086,1124,509,200,360,1160,615,614,528,371,1077,725,1138,152,153,1064,208,1061,523,1059,1058,526,474,802,961,1109,830,134,260,1105,1104,942,1079,610,1046,1007,1044,917,201,200,564,343,505,400,48,315,90,89,54,53,123,1136,1122,881,611,1069,671,614,637,1128,910,431,47,396,424,425,290,1075,878,873,845,128,284,201,792,603,317,316,153,152,1093,336,157,437,49,341,934,611,610,401,291,330,163,256,209,44,431,482,1110,40,1040,1049,1048,374,282,637,505,186,187,646,190,529,528,337,702,439,55,604,601,600,451,553,1056,448,1061,9,479,262,235,134,1078,332,333,329,328,1108,1041,1040,1020,1104,876,186,18,19,1032,961,567,452,535,291,55,95,1024,364,365,256,362,14,88,12,70,69,47,428,334,67,330,331,329,508,455,369,375,122,285,282,474,16,17,244,200,246,290,242,100,101,1099,969,884,1096,1095,770,1092,263,757,364,1046,1024,256,239,238,506,944,509,371,370,287,286,285,280,155,153,956,188,433,1066,702,1063,431,430,364,292,257,96,43,42,11,8,9,672,397,396,125,124,237,160,161,434,841,407,406,438,20,530,666,825,1032,1027,806,701,508,241,200,201,1028,773,614,88,130,640,643,1042,165,716,715,343,160,676,677,157,478,312,1074,211,51,208,372,18,238,330,671,70,293,292,289,247,583,1070,581,130,131,394,878,677,641,640,646,261,260,12,604,509,403,312,283,282,158,155,154,153,53,1024,371,186,331,393,850,583,161,164,130,131,291,290,366,205,244,365,985,751,758,1051,713,719,639,716,605,878},{1665,1664,694,695,1123,1656,560,564,1653,1652,891,811,937,213,611,610,363,954,1644,1279,1277,886,874,711,1632,581,580,194,1043,98,1623,337,1621,1620,1627,1626,1155,1190,762,763,1650,569,538,565,327,321,242,1604,253,1602,1601,1600,616,1551,612,615,614,551,1073,1072,547,546,1628,196,1272,817,1582,635,1584,734,735,1579,1588,540,1590,1591,1592,1593,1594,1595,1088,1378,1598,1206,1606,1145,1241,1603,1602,785,1600,787,1227,1226,909,1224,351,795,258,1547,1546,1545,1544,1555,1556,1366,700,703,1560,1561,691,1563,1564,1565,1303,1073,1587,1586,1585,1584,1583,825,1581,707,653,885,1021,957,192,1549,1507,1270,1196,504,1569,1568,1398,1399,664,665,1526,782,639,1152,1031,1030,905,321,907,1554,1553,1085,983,1550,1549,984,1547,1205,673,672,1543,683,478,479,1539,1538,1537,1536,883,1184,691,690,1490,1491,695,1439,438,439,437,809,938,670,1527,1524,1502,486,1523,1522,650,957,956,1078,982,1508,954,687,1482,1483,1484,1485,1486,1487,1456,1457,1025,1024,1503,1502,1501,1500,1066,1498,1466,753,1266,1494,1493,1295,801,1254,1078,1072,1487,1486,1485,946,1410,549,1450,1258,884,98,955,954,939,1474,1473,1472,1471,1470,1022,1468,1467,1466,1434,1464,1322,1333,771,1349,1236,463,462,1456,1175,1115,1453,1452,1451,1449,1448,1446,1416,1417,616,337,477,410,411,1415,828,1156,1412,1187,1184,1185,1433,1405,1404,1407,803,800,1427,1426,366,362,360,361,430,431,426,1238,1237,1045,1044,516,1413,1075,383,382,381,1408,841,1406,1405,1404,795,1097,1401,1063,1088,1089,1103,1394,124,1350,1127,1349,632,1346,1345,325,1074,1384,1328,1047,1078,1295,1381,1380,1377,1376,820,382,824,1147,1373,1145,313,374,1369,1368,658,1036,531,529,360,361,1322,532,489,488,1352,1351,1350,1338,1339,1336,1337,1076,1049,617,1107,1106,1116,1334,342,343,338,336,345,1320,1094,1068,1071,333,332,1066,1067,1298,1299,1300,326,1302,1303,353,1123,1120,1121,365,424,425,1311,1041,1040,1042,436,420,372,96,500,377,378,1290,1291,499,1293,1294,1295,1315,1098,492,493,542,1310,1089,1088,331,329,328,1258,1270,1169,1301,455,1075,1044,266,1296,1295,549,749,1292,1291,97,467,466,1149,1148,762,175,435,434,1281,1280,1069,1068,1067,1066,1065,361,1168,490,733,246,418,419,416,417,289,147,497,1087,655,640,1115,206,1113,1112,403,342,1259,1258,1256,275,274,1225,1038,465,468,905,335,246,245,125,124,240,1239,1236,1235,178,182,738,177,419,418,227,226,225,224,437,436,1224,1009,69,379,378,498,728,136,537,731,495,492,240,666,211,325,482,361,1090,1116,1169,1118,1187,1237,1236,1077,1074,544,391,550,409,277,276,468,469,465,1156,1157,1203,1159,477,1166,753,758,1216,247,1124,245,254,1212,1173,490,113,364,1184,1077,1076,1075,1074,710,517,516,1080,1086,1087,588,589,1118,72,1112,74,1090,284,285,143,1025,1024,1033,1032,272,219,33,32,121,265,93,271,633,335,1173,1172,1171,1138,1139,1136,1137,613,232,1116}};
  7.  
  8. bool seen[21][2001][1707];
  9. int dp[21][2001];
  10. int N,K;
  11.  
  12. int grundy(int k, int x) {
  13. 	if (x==0) return 0;
  14. 	int& ref = dp[k][x];
  15. 	if (ref != -1) return ref;
  16. 	for (int m=1;m<=k;++m) {
  17. 		for (int i=0;i<=x-m-i;++i) {
  18. 			int ns = grundy(k, i) ^ grundy(k, x-m-i);
  19. 			seen[k][x][ns] = 1;
  20. 		}
  21. 	}
  22. 	for (int i=0;;++i) if (!seen[k][x][i]) return ref = i;
  23. }
  24.  
  25. char s[2005];
  26. int ng;
  27. int groups[2005];
  28. int sp[2005];
  29.  
  30. void determine_winner() {
  31. 	int ret = 0;
  32. 	for (int i=0;i<ng;++i) {
  33. 		ret ^= grundy(K, groups[i]);
  34. 	}
  35. 	if (ret==0) {
  36. 		printf("Johnny wins\n");
  37. 		return;
  38. 	}
  39.  
  40. 	printf("Mary wins\n");
  41.  
  42. 	// Find the best move
  43. 	for (int m=K;m>=1;--m) {
  44. 		for (int i=0;i<ng;++i) if (groups[i]>=m) {
  45. 			//for (int p=0;p<groups[i]-m+1;++p) {
  46. 			for (int p=0;p<=groups[i]-m-p;++p) {
  47. 				int nret = ret ^ grundy(K, groups[i]) ^ grundy(K, p) ^ grundy(K, groups[i]-m-p);
  48. 				//printf("\t\t M: %d GROUP %d, CALL on %d and %d\n", m, i, p, groups[i]-m-p);
  49. 				if (nret == 0) {
  50.  
  51. 					//printf("G: %d, P: %d, M: %d, SP: %d\n", i, p, m, sp[i]);
  52. 					for (int j=sp[i] + p; j < sp[i] + p + m; ++j) {
  53. 						//printf("SET %d to 0\n", j);
  54. 						s[j] = '0';
  55. 					}
  56. 					printf("%s\n", s);
  57. 					return;
  58. 				}
  59. 			}
  60. 		}
  61. 	}
  62. }
  63.  
  64. int main() {
  65. 	memset(dp,-1,sizeof dp);
  66.  
  67. 	/*
  68. 	printf("int precalc[21][]={");
  69. 	for (int k=1;k<=20;++k) {
  70. 		if (k!=1) printf(",");
  71. 		printf("{");
  72. 		for (int n=2000;n>=1400;--n) {
  73. 			if (n!=2000) printf(",");
  74. 			printf("%d", grundy(k,n));
  75. 		}
  76. 		printf("}");
  77. 	}
  78. 	printf("};");
  79. 	*/
  80. 	for (int k=1,i=0;k<=20;++k,++i) {
  81. 		for (int n=2000,x=0;n>=1400;--n,++x) {
  82. 			dp[k][n] = precalc[i][x];
  83. 		}
  84. 	}
  85.  
  86. 	int NCASES;
  87. 	for (scanf("%d", &NCASES); NCASES-- > 0; ) {
  88. 		scanf("%d %d %s", &N, &K, s);
  89. 		int cur = 0;
  90. 		ng = 0;
  91. 		for (int i=0;i<=N;++i) {
  92. 			if (i==N || s[i]=='0') {
  93. 				groups[ng++] = cur;
  94. 				cur = 0;
  95. 			}
  96. 			else {
  97. 				if (cur==0) sp[ng] = i;
  98. 				++cur;
  99. 			}
  100. 		}
  101. 		determine_winner();
  102. 		printf("\n");
  103. 	}
  104. }
  105.

Comments