1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
#include <iostream>
#include <string>
#include <cstdlib>

using std::cin;
using std::cout;
using std::endl;

using IntType = int;

#define DEBUG_LOG if constexpr(false) std::cerr
// #define DEBUG_LOG if constexpr(true) std::cerr << '[' << modeStr << "]: "

#define ENABLE_XOR

std::string modeStr(10, '\0');

const IntType xor_buffer[10][500] = {
    {837,635,919,1521,1784,1718,1839,1938,1376,703,671,240,103,868,589,508,1472,736,609,772,573,104,738,1172,1372,101,1490,609,946,836,1577,832,1313,1086,1622,1331,1704,1506,306,1608,410,202,1161,2032,237,770,1216,953,2021,1441,700,952,845,483,2,60,707,166,1024,892,1851,1381,180,895,1042,1466,109,859,1290,327,1473,161,1579,1659,1800,1678,1552,65,597,1792,59,1255,1178,1081,969,18,1471,994,509,1043,1454,669,1489,1791,1051,490,1430,220,1549,1860,2034,792,456,1721,939,1614,840,522,776,1195,834,1838,307,1051,1764,1713,974,546,1007,1285,524,512,786,1112,1022,1510,1266,1050,974,451,1103,578,763,755,1520,1651,52,1563,512,1256,1352,1028,777,1440,17,1701,1148,1596,812,469,1702,724,99,234,468,920,1678,1241,648,1659,1410,1748,1119,1763,77,1475,34,387,261,304,500,354,1056,1114,1575,1349,83,1337,584,1788,1941,347,1902,144,1865,173,966,604,705,1576,1261,603,319,1105,10,666,1907,1159,2036,1935,153,1218,123,1237,425,520,888,1287,191,1091,395,701,886,1297,796,301,1102,1755,1534,1016,130,1766,1117,471,929,736,466,2011,2012,1627,1028,1625,824,746,224,22,1455,1312,426,968,458,199,1465,1234,1344,1560,862,1580,1728,880,771,1172,1444,1014,602,1097,919,1040,31,1303,1550,155,122,785,1040,1907,1571,892,698,1580,1281,560,1877,785,1753,349,1411,224,1326,432,1623,1063,944,1668,1405,1445,624,63,1304,1904,1362,336,336,949,863,704,1867,1137,209,1442,1974,124,939,711,1379,1276,1434,1933,1595,1775,1217,1724,112,1603,1572,1045,712,2002,656,79,1,991,1911,2008,1833,1824,94,1257,985,1575,1334,65,1689,1915,1272,794,1909,415,1672,500,438,82,348,188,366,23,1162,1491,1017,1886,1021,1963,1339,1158,1982,1178,410,1821,1470,1761,1935,1170,1660,84,1122,1294,730,1788,1433,1526,214,147,1480,1960,440,1672,564,372,645,453,1225,50,40,1971,1360,124,1339,975,119,1729,868,991,530,20,1307,1020,1509,1941,1915,1340,1539,1938,481,444,257,364,1937,67,287,1815,2046,417,304,1013,1321,1014,1782,783,1852,629,571,308,1011,288,1343,2006,936,1853,2044,1961,229,2010,252,792,1869,1297,352,1599,526,1560,1820,198,1285,945,538,1594,1717,858,1591,1634,1012,487,1347,2004,1831,619,352,1329,795,161,1922,284,1066,687,393,171,867,46,1318,1768,2043,1083,851,1489,333,670,1860,1077,785,276,1734,1546,251,1695,818,609,1566,533,1557,1498,1932,1728,283,866,465,1507,1014,508,1461,2015},
    {282,1707,169,695,1569,148,1570,1793,1166,1776,341,1664,1865,617,1583,235,444,1927,1847,1090,1405,1629,919,778,1295,1175,1975,1064,771,768,999,1915,1689,58,640,1295,1570,1548,1956,356,1589,1105,1811,1609,1841,426,1895,1880,461,709,688,382,1882,13,630,1407,67,1635,168,2041,327,303,1769,1086,1858,386,542,176,1874,581,1148,1831,151,1899,1535,301,1121,987,358,2017,330,777,1796,1888,1660,1725,149,1922,353,1240,104,1657,1507,879,1759,1976,1039,1855,1909,886,1815,1422,1979,490,1965,1351,362,764,1086,657,177,92,153,2014,290,1964,1291,1059,289,1050,658,514,1869,1896,1205,717,727,237,1608,1117,67,989,998,503,1462,433,610,1177,1183,1288,1332,1808,883,1338,2026,1455,48,1142,899,195,1658,768,1847,1312,1494,660,1490,785,1127,1235,1725,1851,674,1213,1880,676,1593,1781,640,485,441,125,1300,1320,1571,79,249,1715,301,1039,1261,73,1767,1122,381,136,1327,1329,298,1001,612,784,1139,1215,1268,1163,900,1002,1936,1566,1502,2021,602,368,1917,1794,209,133,1474,1753,785,265,250,1447,129,1512,1603,1222,116,1620,116,1650,144,297,1633,1884,139,1293,1036,1612,1688,575,349,1850,1782,1581,53,42,951,380,548,761,994,982,1700,591,50,1587,1281,2018,1690,1458,166,2009,683,1394,33,254,711,1222,2015,1676,1104,902,1028,718,1816,2016,1398,189,1920,523,1766,1298,1154,1718,901,149,486,740,83,920,1791,821,934,252,1036,1629,1322,62,133,2008,1838,257,1787,911,966,886,1573,333,1119,1286,1826,848,1588,362,529,1275,1876,609,1903,1715,1208,2000,567,368,2020,1423,1299,112,312,1148,2001,435,729,846,396,1272,475,816,101,1339,305,1936,2021,1009,1679,1857,2043,883,717,843,1662,1035,599,1691,742,1992,1512,1169,361,141,1245,379,1954,1010,1532,922,65,1980,1149,1715,1817,1836,385,1793,1374,1388,1802,418,928,1142,12,875,922,491,68,633,1274,923,427,1632,1027,1364,410,420,1421,965,465,614,1692,389,1540,1853,1920,389,1775,1109,1219,1742,816,1794,1004,1860,474,1661,905,912,1252,1199,159,1393,85,1547,1316,2021,829,1080,72,1161,1706,1793,747,1272,1420,1075,1714,91,1393,1874,31,1366,1231,223,1847,948,990,1585,1112,288,151,149,52,738,1395,1424,1413,931,1550,708,1753,841,2005,66,1357,1998,1275,1681,54,1395,1299,58,482,1388,892,1115,101,260,2033,554,1901,762,1326,1465,538,299,332,331,1086,1499,1898,553,464,1645,878,753,593,1124,1005,508,333,296,1869,1785,291,658,337,1041,852,1689},
    {1703,1902,1191,1526,1192,181,870,1608,1413,729,963,374,312,1465,237,1074,798,1387,140,1293,631,784,599,1737,1606,339,1816,1107,885,433,137,1282,1079,472,158,164,1522,1830,745,1702,765,1322,684,1184,998,1114,449,1100,1540,1657,1303,1178,1786,660,1562,1989,582,2029,1809,1402,84,318,1482,766,1859,1858,1016,902,1864,211,706,557,1110,1465,695,1858,1042,1453,1215,921,246,136,1519,439,1400,1794,366,1526,1229,697,1439,1399,374,1189,1568,298,562,1486,1813,1479,917,132,513,1219,929,856,1595,1791,361,1377,1438,119,209,1486,438,643,321,954,1676,612,1718,150,1085,98,1669,1833,812,1602,332,915,1786,1884,1853,631,623,812,1964,1663,257,1031,642,888,1695,756,1626,2044,1076,1231,923,423,1088,1241,1394,528,1917,455,1741,219,1875,650,78,1222,206,73,1127,1084,1621,646,596,1686,1038,272,2008,63,1432,452,1108,1172,625,807,1316,1406,125,1544,582,3,73,814,251,426,132,383,251,1608,1268,1758,1215,983,1419,569,1265,875,529,1681,1208,2000,885,1997,1922,1534,1944,177,650,10,38,636,1550,591,650,1703,641,568,147,1286,126,970,607,290,6,1161,32,1078,10,1066,887,648,1404,895,1637,472,1597,1449,1029,1668,2040,1258,1724,555,1805,155,1772,987,1667,1480,510,1896,1405,372,248,357,1736,26,1770,760,447,426,1629,1039,1129,1579,979,787,1577,241,93,1312,1452,1304,6,414,2014,924,1231,1289,1934,1874,1511,1063,1397,574,705,229,1062,1837,736,1169,346,335,1163,961,2037,873,1501,674,1995,1287,686,101,1797,1983,535,754,1246,302,19,1154,812,1841,1736,1849,412,8,1719,598,1916,1155,689,263,1795,1549,256,968,1338,706,507,1672,1824,1616,1758,154,512,187,1779,276,773,869,2015,316,293,1598,615,1993,847,1859,2020,1963,1214,1856,1739,469,179,1743,332,684,479,259,129,846,448,1062,976,993,880,906,818,973,2017,1915,1187,919,1300,612,1313,1960,1636,1330,1637,1665,807,1512,1035,188,1385,857,1819,1819,598,1291,1362,176,262,1331,1612,1173,1775,764,800,1423,368,112,332,1614,1018,190,1319,836,42,1198,350,1158,190,477,1586,951,1310,839,545,1256,817,1991,1509,478,1690,1342,1364,169,996,789,116,1442,1820,1503,2038,714,1493,944,910,314,224,1217,2,757,642,1656,440,337,158,1360,733,1074,1545,1700,310,1540,892,1230,1785,1783,129,933,1423,167,1272,706,144,1394,1941,1999,85,701,1068,1879,1267,628,1017,1694,1499,1276,113,1462,1926,1550,1064,1347,1528,1724,1753,481,2029,992},
    {2017,260,0,1146,1222,1223,1261,1415,59,1833,1627,576,479,1913,780,146,238,505,85,1869,135,193,1404,721,1692,1583,136,465,1084,1856,181,1650,1584,239,132,1102,725,1791,1271,1488,424,1235,360,819,963,14,365,551,1648,1760,214,1803,1865,1344,1682,1842,597,148,703,1897,1086,1156,1679,586,1207,422,1031,535,949,1803,43,1347,59,242,79,91,749,1924,371,1279,910,1989,1703,504,1348,1519,1238,1118,62,1956,1449,1303,1920,1470,852,180,1588,289,553,1391,1577,528,1345,1054,1489,1062,694,1865,1628,1032,1472,1562,126,726,454,524,279,1714,1443,1755,1777,630,235,1142,1207,1442,408,1520,877,1265,389,732,1368,135,1892,60,1925,1066,612,1567,1389,1195,1883,1377,1030,881,451,1008,280,621,8,1939,469,1275,970,1864,1292,1421,1848,1271,831,1798,291,1973,669,405,301,2028,1691,656,1654,1139,1420,1974,1321,37,1399,1354,1959,824,1181,188,834,316,1716,1713,709,1980,1910,733,1717,1998,175,1054,1177,1582,1732,1701,270,230,341,1933,364,1679,1469,914,1983,1472,602,541,153,946,817,635,2034,1386,1607,982,753,49,1301,288,1083,1294,1587,1295,1436,375,1561,1476,444,1077,1497,1673,92,1528,467,607,1782,491,605,874,1657,1314,896,109,1496,1622,1482,1306,1337,789,292,1106,1236,725,1611,108,70,1807,1925,383,48,237,1320,1861,997,376,1613,183,210,444,786,177,1740,1560,1190,1505,758,782,1646,160,652,174,952,22,1650,243,1488,986,1158,790,111,1786,758,1453,141,1127,1705,1079,1429,876,412,274,127,344,678,1242,1979,1475,1647,1240,766,1800,94,746,1217,829,1125,1228,1571,67,1788,1764,1367,916,1656,958,1293,83,477,1971,210,86,810,1913,777,1257,1568,1585,704,1462,848,85,777,820,1296,76,1573,800,1138,1535,814,805,1521,1912,344,1028,1402,596,1038,1374,1665,0,1391,1342,1380,1043,477,1393,1213,1634,1153,525,1609,1905,850,1389,166,1868,1971,566,1107,806,858,1936,683,1964,1486,1763,1192,1025,1238,1659,167,944,172,1184,1048,1942,515,849,451,1075,1329,910,510,1376,52,470,395,678,375,1289,1511,313,815,328,226,1871,419,911,1652,1493,1224,1134,356,1844,1101,1880,560,1568,993,1551,1714,113,395,885,980,460,1540,1876,1116,881,4,1913,1710,1984,1228,1562,945,1228,121,929,1150,1438,253,262,1743,288,1265,3,679,35,6,573,1748,1049,1355,343,1337,1779,1481,1527,1263,259,1513,453,312,1087,1080,2035,967,236,1181,566,1192,877,383,1354,889,395,1615,1102,86,786,532,973,2041,699},
    {163,430,1177,1290,14,1292,1864,714,2033,1876,274,976,25,1636,78,1791,1938,899,720,1305,834,1708,523,539,1102,2010,1450,256,1111,1960,1955,93,1281,1429,211,259,1623,2042,1324,2028,1550,844,1640,1405,236,803,87,620,594,743,2036,517,353,1625,1178,1432,611,1260,495,285,1825,385,1905,1599,497,185,382,774,882,514,1665,1958,1322,55,1683,1079,712,1338,41,362,1935,1058,1913,1143,1440,1564,247,941,1946,1402,1236,1679,408,1863,1832,1956,1093,792,343,1444,225,127,1890,1320,1451,1746,1680,789,431,1383,69,1078,311,1015,214,701,350,613,1352,812,1211,426,571,1652,622,422,1364,1737,323,126,1368,1717,910,1299,1955,493,488,1411,1716,726,1748,332,420,1161,1433,883,216,1621,1584,653,1064,2024,1141,824,944,1056,636,1874,1056,948,372,302,732,1795,1577,1440,186,1626,1138,906,269,1856,884,1666,411,249,1148,348,933,2013,35,422,710,1276,1080,470,852,1524,887,508,92,2014,1559,1905,1916,1644,1627,1538,64,105,1531,1656,1530,909,532,921,627,816,2033,1704,307,617,657,648,1536,235,2008,1021,744,1671,1644,496,1280,1692,677,541,1906,850,568,965,926,2005,305,409,260,976,1398,575,1786,752,816,149,1960,538,164,427,926,1423,328,1863,819,1397,1961,333,1858,1396,490,1865,82,1689,262,1216,1727,1489,776,135,1505,1467,820,948,1709,533,89,217,1295,547,490,1910,1196,209,1460,25,339,906,615,564,2036,887,624,296,1742,864,1628,674,1012,1229,1309,1416,937,153,1119,62,2011,1000,997,220,180,1054,1833,987,1493,1605,1132,943,619,762,1412,678,1015,1313,1929,3,513,867,583,736,714,1241,986,1749,2017,1948,159,10,1192,99,666,1467,145,132,778,910,382,1587,1196,1878,587,1702,1222,1187,163,1670,1176,178,362,1112,958,1231,468,970,1552,579,1802,1790,412,1602,1355,1320,156,212,1503,1379,550,271,1717,854,1425,1599,98,23,1902,511,1683,723,827,1119,1003,806,1014,1831,321,1479,1546,461,1787,352,124,478,391,173,57,1163,274,2009,1233,1609,182,548,1217,1492,652,1031,876,1565,1648,924,373,1581,1175,1527,1351,1078,724,324,2036,528,418,1099,662,938,1583,1171,246,410,794,1970,1846,158,1513,38,205,883,1382,1389,1320,1011,133,1076,1802,1292,1140,1600,1945,1185,389,420,1830,177,1621,299,744,1734,329,50,1449,966,396,648,1145,845,1829,893,209,1033,52,307,1694,59,1814,192,1142,1774,1628,215,1544,322,455,1653,815,1955,1854,304,1395,429,678,1636,1030,1236,284,730},
    {148,1624,1710,6,1199,962,240,298,1516,549,1050,887,8,266,1103,568,1526,1958,1490,1354,1913,968,1323,1961,1545,2001,368,1177,1560,846,992,458,1237,110,1650,279,768,1853,426,1625,956,461,612,1372,1373,583,257,329,447,479,539,890,1704,2035,1118,457,238,471,1336,1456,1484,956,1794,446,336,1715,1573,969,1040,50,942,582,788,315,743,166,1016,692,1898,317,558,297,719,1997,739,1638,565,1393,1913,1464,600,1689,782,727,1498,1391,2025,1734,1416,1683,1062,253,1507,1520,1848,499,1207,1180,1190,1406,1499,1461,229,1781,1026,1084,443,1660,763,467,1200,1089,1709,939,1423,854,1664,1022,1614,185,198,698,319,1152,1835,2030,1739,108,648,1151,1053,1540,338,806,1833,1390,901,903,673,2027,1790,986,83,1503,1016,201,1278,242,1459,1852,1689,1577,864,641,601,1576,893,888,557,606,1737,1135,254,903,1132,220,409,838,144,7,601,653,1263,863,1037,1487,49,475,1472,1133,1337,844,629,1244,745,147,1560,1117,8,187,1334,1322,1914,345,751,1101,1621,17,944,454,429,1223,2,194,437,1571,1749,437,1545,494,1120,1664,1083,1640,1777,1599,1097,419,1774,1207,1656,1186,1581,1974,897,132,1509,536,1816,652,555,1762,1865,362,1381,126,1673,1761,514,231,695,955,101,1743,1911,846,1445,281,68,256,1859,118,14,1933,500,909,1661,262,1717,1263,1009,899,899,1285,61,1386,1876,341,744,118,481,631,1240,1901,615,1631,1607,875,1734,1088,1330,829,1166,1067,1785,1479,416,1880,801,1545,1378,1959,32,1533,1035,1316,1609,434,1512,1240,399,1250,1497,368,82,1817,37,1048,723,783,1581,1389,1299,945,1671,594,1307,1642,1594,1292,1122,1330,941,2020,2029,822,1942,82,1266,1744,1955,566,194,1013,700,1910,1311,145,1114,2040,1450,54,1259,959,1477,664,1969,340,1208,1318,65,386,800,2031,699,1981,1479,1844,1897,789,545,1322,650,1138,2047,673,565,642,210,938,1771,1775,429,1676,887,346,1377,676,1515,474,881,1369,223,2037,1680,135,1541,59,163,463,1480,1911,855,1112,458,1874,611,1067,1476,1885,1557,426,1905,1519,1648,2021,846,1465,1001,1676,1150,1203,1346,423,87,1654,1045,1083,1050,1570,340,1324,1556,1185,460,289,1571,1272,659,222,383,1185,1116,655,1829,653,282,2042,396,2022,207,423,1712,164,6,1303,1449,1954,1175,1195,1706,1733,57,1740,646,1785,1809,45,1808,2041,253,1870,1257,677,623,1110,1746,369,1150,515,2031,1258,1775,1971,1374,601,1090,2044,148,1499,1238,202,624,795,1611,282,1106,615,1878,948},
    {288,673,1625,675,365,1558,527,1057,387,860,1909,1672,1495,1453,1206,1722,1633,1732,988,1918,897,230,772,407,1602,1466,1312,1187,762,1245,1794,1540,1110,1371,1093,559,226,135,483,628,1636,296,413,824,1367,530,338,415,59,62,813,1055,266,888,876,1231,1954,1722,974,487,1850,1176,367,1013,1232,1561,1135,1967,956,1098,1647,24,1631,812,147,361,420,1300,155,838,1148,1404,1479,608,781,500,1533,1967,1793,1500,494,1238,1508,1704,1960,110,1371,1424,1869,1473,479,106,1799,1078,1133,1716,705,113,819,883,644,1519,759,770,383,503,1416,1070,265,1127,1850,1869,1812,1915,1006,1274,486,1656,827,1397,1985,436,69,1324,169,757,1863,1334,252,938,1326,486,74,909,2016,1021,510,461,24,442,1502,869,838,1212,1505,14,104,790,1936,1563,68,440,910,1107,1480,227,955,1992,632,253,1555,1986,1971,1506,1382,1756,591,1543,178,1804,1228,1730,1709,528,920,1115,1042,722,719,1290,1939,154,656,1177,1385,842,1662,201,189,646,287,1649,1884,444,1187,1068,1840,518,1150,55,1607,1923,387,1544,955,1751,1173,1027,566,147,702,1417,984,1670,628,1696,904,1361,1865,334,1846,2030,935,902,1319,982,523,292,1968,1517,571,2011,915,1597,815,1643,1169,867,1565,1734,850,1979,1348,1088,1835,568,809,1295,2041,1635,1731,1469,1233,243,2009,1985,814,1620,360,1904,1142,811,626,2000,1118,220,813,674,323,1226,1570,792,1909,1879,185,294,1911,1803,119,853,2045,1934,271,83,1451,760,530,1320,1243,1517,925,2040,1339,1181,174,75,761,1672,1503,1188,1336,1094,1604,148,1447,1292,923,904,618,1197,1555,1452,2011,1035,1325,1013,1736,1282,1631,1472,733,1522,263,295,446,1349,470,1075,615,339,1500,1878,1491,595,1240,331,1922,712,1459,6,401,362,2008,1906,1030,1598,715,571,1825,1723,1746,1216,907,1817,1301,651,2020,1891,2035,869,533,1290,594,1239,772,111,1644,264,1824,231,529,482,1042,279,1355,859,1412,340,1072,329,221,1335,81,1368,1668,194,1137,449,1569,1822,1985,313,662,1837,1661,1546,1043,411,1747,1596,157,298,515,1099,31,1384,54,1397,180,979,1366,834,956,289,1141,1821,847,2022,419,1170,1629,1890,1040,377,1523,1509,760,350,595,1541,27,769,64,638,1571,1550,1060,1117,718,627,994,1229,967,1717,1280,267,1833,914,640,1703,1642,1789,1751,1575,1705,1750,528,1021,1576,1349,582,2022,371,1765,2011,376,365,1357,1255,596,1243,504,990,1227,383,1797,200,1161,1388,117,1456,1018,1208,4,1423,1297,1581,1631,345,1240},
    {191,1747,786,1292,1420,1739,748,1229,725,1869,1998,1421,981,851,1760,536,1869,2041,868,1077,754,1682,777,18,1635,236,1918,2001,204,339,1954,1533,125,370,127,1101,1282,1646,959,128,180,1937,651,2005,380,1784,1196,1041,455,1130,408,1566,23,832,1405,1501,419,1514,2022,1537,1038,1241,1048,1559,812,608,965,1900,1018,886,334,888,1461,15,1347,1742,793,1808,48,1802,1353,1394,1742,1025,1500,914,1436,1322,1823,1762,876,1812,909,749,324,1956,792,96,1288,237,1949,864,214,763,279,1016,896,1335,1623,1557,1154,1763,131,553,152,1114,899,1154,940,808,592,1993,1027,728,1389,697,1945,2024,891,1360,582,1791,1748,1961,1195,1216,1233,737,932,1737,1452,353,1671,130,441,317,1836,66,1964,455,1973,121,745,286,1990,501,1570,1993,1324,1881,530,1726,1539,505,1359,248,1193,1216,1813,103,1175,495,148,131,1114,1360,1690,519,317,160,1584,1310,378,1919,1810,1317,554,1950,571,1100,1409,329,260,198,718,1415,619,813,1873,1463,1226,584,401,232,221,1983,777,1786,21,1824,1928,1281,753,1922,632,758,319,1063,1980,1158,1937,263,211,206,2016,333,106,1286,428,1633,974,2013,1611,460,184,613,1900,528,870,1654,75,472,1472,1203,763,15,903,258,85,683,228,305,674,309,1811,965,821,1853,1427,818,1014,1050,1144,891,481,874,447,303,1087,1267,1381,349,289,1724,1755,1646,1449,1880,476,1322,638,1054,1541,1521,2019,744,700,485,741,1448,36,1604,1911,1756,1834,528,1543,1193,139,392,1459,485,792,1954,437,749,1765,686,49,304,1013,1924,584,679,1806,1338,1961,436,300,157,1616,1711,1785,1945,223,1430,476,1667,1189,1785,174,353,1456,486,1763,1568,1770,1701,1905,495,2028,451,1155,845,304,1688,203,427,1131,237,1042,1682,474,717,987,123,489,854,1576,326,754,836,1130,1885,729,1881,1782,2005,900,430,814,490,1613,1444,463,1115,1489,1290,1362,1874,1293,271,728,1504,192,892,1806,923,1166,1226,1994,408,1724,1255,830,394,165,967,447,559,1115,1913,1012,21,1550,573,442,9,221,1851,507,1196,1495,1488,1105,1181,308,192,451,1976,828,1258,533,551,609,1743,1593,922,375,416,392,383,1374,135,1240,1543,694,369,888,2000,344,992,992,177,184,601,361,1710,1598,1930,499,1283,1987,631,192,117,1669,1226,1075,1395,1275,1783,1671,146,23,758,916,319,688,740,1329,795,1779,185,9,606,1912,832,1713,144,809,1106,950,1051,1919,260,1834,1915,1957,1348,1538,1518,1720,662,1257,587,1381,520,630,1413},
    {1939,649,204,1445,994,1222,179,112,59,498,1362,1799,1434,790,230,1351,886,1105,1641,1818,1559,522,1556,1369,1468,1355,1946,1831,457,112,1741,44,1791,972,97,735,544,685,1537,1911,1355,508,1837,1803,502,347,1891,974,1375,663,439,1208,709,1747,196,1126,1227,1421,418,201,843,708,976,998,866,1630,1815,1895,745,1245,21,676,1880,76,1130,580,1065,1478,1822,426,1762,265,1112,1748,1152,1837,1699,81,628,583,1994,1899,1608,371,886,664,1138,978,56,734,1816,412,397,1022,1135,1720,1493,1002,1234,374,1759,369,1368,1412,1610,1882,964,762,1003,723,1270,588,279,936,711,473,1954,995,1342,1596,1010,186,339,1106,1591,1394,1645,1605,1532,248,562,1723,1520,997,244,549,998,456,1448,499,1891,1197,1082,628,1741,1617,1878,1309,1486,770,401,988,845,771,1835,295,1889,1982,1398,1786,366,1114,1066,206,1884,1537,1921,1745,811,977,964,2001,489,365,1375,170,511,293,1245,44,409,1485,1609,401,81,57,284,1131,792,400,766,968,1545,1845,163,1674,981,628,218,1103,926,160,1058,193,1058,1973,1644,1323,1002,1540,1090,1570,1138,524,806,1765,1799,1360,993,278,269,405,295,1523,437,41,270,863,1131,1145,896,926,594,1998,856,1123,31,1416,1709,1876,781,488,1408,99,1295,923,1954,1652,795,524,584,1252,1091,78,346,464,688,623,375,918,2025,721,288,1510,1969,1805,1695,110,735,753,1716,1229,2032,997,732,30,567,472,1515,1326,833,426,60,1374,769,94,180,1671,841,914,1456,1918,1443,121,183,661,1311,801,773,1931,775,931,1322,2047,1895,330,1911,1435,1202,1842,265,235,1417,1955,1552,160,1684,781,632,656,1474,1019,531,288,2030,1659,672,971,476,1536,1146,1106,1145,1051,1178,890,1352,12,1041,274,569,420,1704,383,1939,1944,814,1154,473,1035,1505,27,499,678,1796,807,827,186,1988,1160,805,1375,274,1265,841,709,1272,785,911,932,1015,109,1278,1952,140,943,1085,1011,1850,1176,837,1150,1014,1284,414,138,699,1627,627,1919,1065,1809,300,869,713,1342,57,1268,421,99,1438,1671,1522,1440,1746,780,1412,1321,297,388,1797,87,440,1522,407,1003,201,1201,426,1206,585,1864,1232,1971,501,1176,951,1378,1627,472,485,251,269,242,1140,1597,1936,239,456,1011,1581,1606,288,1125,941,1165,1772,1512,510,1310,272,628,1841,398,1579,1710,627,431,509,147,191,997,22,1156,739,46,1055,886,740,994,905,399,867,347,1403,1982,883,1160,586,903,55,320,449,1326,1160,1806,1074,1089,1096,611},
    {595,1389,1761,468,654,1613,306,1874,1708,184,1555,1060,1192,1611,1043,1385,103,1533,545,571,1018,1305,153,1142,946,957,878,1426,1655,1660,1293,1082,1636,1023,777,446,1330,1044,641,964,721,1160,645,340,391,290,324,1055,1358,1585,53,2027,1042,74,330,133,2002,1760,1755,444,435,553,24,1298,1298,615,424,1565,594,1028,1569,1411,2010,1768,287,986,1550,532,607,492,1607,1224,1425,371,1378,1534,1245,1395,4,992,208,865,259,1341,256,1874,407,1049,1251,924,438,997,537,951,956,54,418,350,214,888,1406,840,519,1051,1429,1488,39,374,962,1973,1512,1020,1894,160,616,1098,955,641,1588,1229,235,781,1811,1586,1504,348,9,68,1454,20,1597,1485,746,2018,217,237,1892,506,422,1831,1279,1961,1699,983,1569,58,916,1505,1575,20,440,832,1844,94,2043,1286,845,299,326,144,1693,685,747,1411,927,1289,920,655,1712,1816,2032,1642,1863,612,1115,1972,1418,851,605,1499,977,241,1357,1544,1976,1830,1982,1624,1144,39,776,1571,873,1558,12,1022,538,141,1319,131,1313,688,870,421,977,1497,546,2041,1470,1949,485,1133,1878,1347,680,380,177,1410,1795,1773,1348,410,1466,1151,441,345,1249,1411,1457,112,1077,461,304,1951,926,1839,1659,359,306,527,120,1306,873,505,1712,751,1133,1297,1686,394,195,1040,279,2040,857,418,2036,1807,381,595,1195,181,631,1140,1873,1269,383,726,628,74,1345,1326,1807,1319,154,1887,917,1197,862,388,1483,1524,539,1062,1112,1204,1048,1504,1320,1971,1188,1380,564,1525,1209,120,1826,801,754,757,608,934,849,413,2015,1098,1261,1659,220,1500,739,290,195,116,84,951,0,967,1473,1876,364,1734,1616,520,1121,1334,1370,680,1503,686,1890,1079,1791,350,1939,247,1173,1604,1987,1403,1312,1468,1724,1614,1246,1509,1139,303,1708,341,532,289,1863,1764,44,1728,411,1876,682,1005,423,1481,1352,1340,1119,793,1015,468,1054,1554,397,353,1233,1586,1784,767,977,317,1876,1695,669,224,1605,5,1704,407,1804,573,606,2045,194,112,1424,1710,1538,1810,809,1397,1962,1104,1497,153,1324,434,1523,363,197,1789,539,162,62,1643,1296,1755,371,921,570,521,1897,1824,626,61,1324,1571,457,474,2018,317,884,2013,1493,263,1907,477,807,768,1189,251,729,1167,1218,1000,335,1415,657,403,709,557,1234,575,794,1797,897,946,287,1718,1156,360,418,1342,721,1049,1153,1104,1838,1402,142,468,306,1594,1854,1601,1946,1274,1740,236,461,882,563,1953,38,325,2000,263,456,998,1203,102,1552,1706},
};

IntType parse(const char *ptr, int n) {
    IntType ret = 0;
    IntType decimal = 1;
    
    for (int i = 0; i < n; ++i, decimal *= 2)
    {
        ret += (ptr[i] - '0') * decimal;
    }

    return ret;
}

void dump(char *ptr, int n, IntType value) {
    IntType decimal = 1;
    
    for (int i = 0; i < n; ++i, decimal *= 2)
    {
        if ((value & decimal) != 0)
        {
            ptr[i] = '1';
        } 
        else
        {
            ptr[i] = '0';
        }
    }
}

const constexpr char SIGNS[] = "PKN";

char play(char c)
{
    DEBUG_LOG << "Send: " << c << endl;

    cout << c << endl;
    cin >> std::skipws >> c;

    DEBUG_LOG << "Got: " << c << endl;
    return c;
}

void test(const int myMode, const int opponentMode, std::string text)
{
    constexpr int STEP_IN = 11;
    constexpr int STEP_OUT = 7;

    const int n = text.size();

    text += std::string(STEP_IN, '0');
    std::string other(n + STEP_IN, '0');
    
    for (int i = 0; i < n; i += STEP_IN)
    {
        auto value = parse(text.data() + i, STEP_IN);

#ifdef ENABLE_XOR
        value ^= xor_buffer[myMode][i / STEP_IN];
#endif

        IntType otherValue = 0;
        IntType decimal = 1;
        
        for (int j = 0; j < STEP_OUT; ++j, decimal *= 3)
        {
            const char myPlay = SIGNS[value % 3];
            value /= 3;
            
            DEBUG_LOG << "Transfer digit [" << i << " / " << j << "]" << endl;
            const char opponentPlay = play(myPlay);

            if (opponentPlay == 'K') otherValue += decimal;
            if (opponentPlay == 'N') otherValue += 2 * decimal;

            DEBUG_LOG << "Current otherValue = " << otherValue << endl;

            int score = 0;

            if (myPlay == 'P' && opponentPlay == 'K') score += 1;
            if (myPlay == 'P' && opponentPlay == 'N') score -= 1;
            if (myPlay == 'K' && opponentPlay == 'P') score -= 1;
            if (myPlay == 'K' && opponentPlay == 'N') score += 1;
            if (myPlay == 'N' && opponentPlay == 'P') score += 1;
            if (myPlay == 'N' && opponentPlay == 'K') score -= 1;

            DEBUG_LOG << "Score = " << score << endl;


            if (score == 1) play('K');
            if (score == -1) play('P');
        }

#ifdef ENABLE_XOR
        otherValue ^= xor_buffer[opponentMode][i / STEP_IN];
#endif

        dump(other.data() + i, STEP_IN, otherValue);

        DEBUG_LOG << "Updated other = " << other << endl;
    }
    
    other.resize(n);
    cout << "! " << other << endl;
}

int main()
{

    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int n_tests, length;
    cin >> modeStr >> length >> n_tests;

    std::string text(length+10, '\0');

    const int mode = (modeStr == "Algosia" ? 0 : 1);
    const int mode2 = 1 - mode;

    for (int i = 0; i < n_tests; ++i)
    {
        cin >> text;

        test(2 * i + mode, 2 * i + mode2, text);
    }
}