{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv class\u003d\"problem_par\"\u003e\u003cdiv class\u003d\"problem_par_normal\"\u003eAlice and Bob are playing with \u003ci\u003ek\u003c/i\u003e-dimensional rectangular parallelepiped\r\nconsisting of \u003ci\u003en\u003c/i\u003e\u003csub\u003e1\u003c/sub\u003e × \u003ci\u003en\u003c/i\u003e\u003csub\u003e2\u003c/sub\u003e × … × \u003ci\u003en\u003csub\u003ek\u003c/sub\u003e\u003c/i\u003e unit hypercubes.\r\nThey make moves in turn. Alice chooses some unit hypercube, and cuts\r\nthe parallelepiped through the center of this hypercube with all possible\r\nplanes that are parallel to its sides. All unit hypercubes that were\r\ncut by at least one plane are removed, and what remains is a series of smaller\r\nrectangular parallelepipeds. It is required that at least one of those\r\nsmall parts has edge lengths that are pairwise relatively prime with \r\nthe corresponding edge lengths of the original parallelepiped. It is also allowed\r\nto cut the parallelepiped in such way that no parts remain.\r\n\u003c/div\u003e\u003c/div\u003e\u003cdiv class\u003d\"problem_par\"\u003e\u003cdiv class\u003d\"problem_par_normal\"\u003eAfterwards, each player chooses any of remaining parallelepipeds, and cuts\r\nit as described above. After a cut every parallelepiped is left,\r\nand making the turn the player can choose any of them.\r\nThe player who can\u0027t move loses. Assuming\r\nboth players play optimally, who will win?\r\n\u003c/div\u003e\u003c/div\u003e\u003cimg src\u003d\"CDN_BASE_URL/9df28449e968d18e80692dfac70a83e5?v\u003d1716043711\" border\u003d\"0\" alt\u003d\"Problem illustration\" align\u003d\"RIGHT\" class\u003d\"problem_raimage\"\u003e\u003cdiv class\u003d\"problem_par\"\u003e\u003cdiv class\u003d\"problem_par_normal\"\u003eLet\u0027s consider an example. Assume that \u003ci\u003ek\u003c/i\u003e \u003d 2, and we have a 6 × 5\r\nrectangle. By cutting the hypercube at (1, 4) we get two parts:\r\n5 × 1 and 5 × 3. As the second part\u0027s (as well as first part\u0027s,\r\nbut that\u0027s not important) edge lengths are relatively prime with\r\nthe edge lengths of the original rectangle (5 is relatively prime with 6 and\r\n3 is relatively prime with 5), this is a possible move. However,\r\ncutting the hypercube at (3, 2) is not a possible move, because each of the remaining\r\nparts (2 × 1, 3 × 1, 2 × 3, 3 × 3) doesn\u0027t satisfy\r\nthe condition above.\r\n\u003c/div\u003e\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cdiv class\u003d\"problem_par\"\u003e\u003cdiv class\u003d\"problem_par_normal\"\u003eThe first line of the input contains an integer \u003ci\u003ek\u003c/i\u003e (1\u0026nbsp;≤\u0026nbsp;\u003ci\u003ek\u003c/i\u003e\u0026nbsp;≤\u0026nbsp;8), \r\nthe second line contains \u003ci\u003ek\u003c/i\u003e integers \u003ci\u003en\u003c/i\u003e\u003csub\u003e1\u003c/sub\u003e, \u003ci\u003en\u003c/i\u003e\u003csub\u003e2\u003c/sub\u003e, … \u003ci\u003en\u003csub\u003ek\u003c/sub\u003e\u003c/i\u003e, \r\n1\u0026nbsp;≤\u0026nbsp;(\u003ci\u003en\u003c/i\u003e\u003csub\u003e1\u003c/sub\u003e+1) × (\u003ci\u003en\u003c/i\u003e\u003csub\u003e2\u003c/sub\u003e+1) × … × (\u003ci\u003en\u003csub\u003ek\u003c/sub\u003e\u003c/i\u003e+1)\u0026nbsp;≤\u0026nbsp;10000.\r\n\u003c/div\u003e\u003c/div\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cdiv class\u003d\"problem_par\"\u003e\u003cdiv class\u003d\"problem_par_normal\"\u003eOutput the number of the winning player to the first line of output \r\n(1 for Alice, 2 for Bob). In case Alice wins the game, output the\r\nfirst move that leads her to the win to the second line of output.\r\nThe move is described by \u003ci\u003ek\u003c/i\u003e numbers, 1-based coordinates of the\r\ncut hypercube. In case there\u0027re several possible moves that lead her\r\nto the win, output the lexicographically smallest one.\r\n\u003c/div\u003e\u003c/div\u003e"}},{"title":"Sample","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e2\r\n2 2\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e2\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003cbr\u003e\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e3\r\n3 4 5\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e1\r\n1 1 3\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}