aboutsummaryrefslogtreecommitdiff
path: root/Puzzle12.hs
blob: a63d4a9e584f85c6ef28ab468b5306660294a3f6 (plain) (blame)
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
import Data.Set (Set)
import qualified Data.Set as Set
import Data.List.Split (splitOn, splitOneOf)

f :: ([Int], Set Int) -> ([Int], Set Int)
f (xs, ys) = (Set.toList $ zs Set.\\ ys, ys `Set.union` zs)
  where zs = Set.fromList $ mconcat $ fmap (\x -> cs !! x) xs

solve1' :: Int -> Set Int
solve1' x = snd $ until (null . fst) f ([x], Set.fromList [x])

solve1 :: Int
solve1 = (Set.size . solve1') 0

allGroups :: (Int, Set Int) -> (Int, Set Int)
allGroups (n, xs) = (n + 1, xs Set.\\ (solve1' $ head $ Set.toList xs))

solve2 :: Int
solve2 = fst $ until (Set.null . snd) allGroups (0, Set.fromList [0 .. length cs - 1])

removeJunk :: [Char] -> [Int]
removeJunk = (fmap read) . tail . (filter (not . null)) . (splitOneOf " <->,")

parseInput :: [Char] -> [[Int]]
parseInput = (fmap removeJunk) . (splitOn "\n")

--cs = parseInput test
cs = parseInput input

test = "0 <-> 2\n1 <-> 1\n2 <-> 0, 3, 4\n3 <-> 2, 4\n4 <-> 2, 3, 6\n5 <-> 6\n6 <-> 4, 5"
input = "0 <-> 412, 480, 777, 1453\n1 <-> 132, 1209\n2 <-> 1614\n3 <-> 3\n4 <-> 1146\n5 <-> 5, 528\n6 <-> 107, 136, 366, 1148, 1875\n7 <-> 452, 701, 1975\n8 <-> 164\n9 <-> 912, 920\n10 <-> 152\n11 <-> 1109\n12 <-> 1282\n13 <-> 17, 793\n14 <-> 1665\n15 <-> 21, 1413\n16 <-> 233, 1297\n17 <-> 13\n18 <-> 506\n19 <-> 1709\n20 <-> 1526\n21 <-> 15, 59, 106\n22 <-> 756, 923, 1698\n23 <-> 94, 191, 206, 443\n24 <-> 24, 1996\n25 <-> 495\n26 <-> 572\n27 <-> 920, 1127\n28 <-> 447, 1304\n29 <-> 29, 142, 474, 552, 1089\n30 <-> 259\n31 <-> 840, 1224\n32 <-> 1839\n33 <-> 653, 1054\n34 <-> 856, 1185\n35 <-> 842\n36 <-> 1172, 1247, 1676\n37 <-> 666, 1606\n38 <-> 414, 650\n39 <-> 238, 1344\n40 <-> 331, 1517\n41 <-> 276, 631\n42 <-> 953, 1096\n43 <-> 872\n44 <-> 882, 1274\n45 <-> 980, 1600\n46 <-> 800, 1372, 1978\n47 <-> 394, 662, 1442\n48 <-> 924, 1229, 1759, 1838\n49 <-> 112\n50 <-> 50, 852, 1751\n51 <-> 310, 591, 920\n52 <-> 313, 779\n53 <-> 922, 1702\n54 <-> 54\n55 <-> 648\n56 <-> 402\n57 <-> 926, 1169\n58 <-> 731, 1007, 1129, 1629, 1659\n59 <-> 21, 602\n60 <-> 1159\n61 <-> 61, 683\n62 <-> 803, 1232, 1348, 1720\n63 <-> 1012, 1461\n64 <-> 542, 965\n65 <-> 640, 665\n66 <-> 761, 1001\n67 <-> 782, 1813\n68 <-> 68\n69 <-> 133, 651\n70 <-> 1827\n71 <-> 217\n72 <-> 491, 1862\n73 <-> 295\n74 <-> 282, 964\n75 <-> 710, 1075, 1194, 1411\n76 <-> 263, 1027, 1877\n77 <-> 597, 846\n78 <-> 880, 983, 997\n79 <-> 1398\n80 <-> 1023, 1812\n81 <-> 370, 1120, 1312\n82 <-> 1840, 1979\n83 <-> 691, 1603\n84 <-> 84, 182\n85 <-> 928\n86 <-> 666, 1274, 1310, 1479\n87 <-> 861, 1065, 1595, 1777\n88 <-> 1588\n89 <-> 1877\n90 <-> 1305, 1458, 1531\n91 <-> 456, 1115\n92 <-> 1167, 1396\n93 <-> 617\n94 <-> 23\n95 <-> 508, 1260\n96 <-> 1622, 1912\n97 <-> 97\n98 <-> 995, 1589\n99 <-> 474\n100 <-> 218, 1018\n101 <-> 1335\n102 <-> 675, 1368\n103 <-> 1013\n104 <-> 832, 1730\n105 <-> 950\n106 <-> 21, 1008\n107 <-> 6, 998\n108 <-> 108\n109 <-> 109, 368, 941\n110 <-> 417, 502, 865\n111 <-> 1459, 1967\n112 <-> 49, 1931\n113 <-> 767, 790, 1367\n114 <-> 1347, 1421, 1879\n115 <-> 707, 1714\n116 <-> 116\n117 <-> 154, 1431\n118 <-> 327, 1062\n119 <-> 1461\n120 <-> 1088\n121 <-> 434, 1659\n122 <-> 841, 930, 1222\n123 <-> 1960\n124 <-> 360, 416, 536, 961, 1498\n125 <-> 946, 1455, 1992\n126 <-> 512, 1694\n127 <-> 1131, 1201\n128 <-> 311\n129 <-> 129, 718\n130 <-> 1138, 1905\n131 <-> 620\n132 <-> 1, 255, 1275\n133 <-> 69, 589\n134 <-> 729, 1002, 1842\n135 <-> 1956\n136 <-> 6, 1135\n137 <-> 367, 375\n138 <-> 138, 494\n139 <-> 1750\n140 <-> 1082, 1501, 1688\n141 <-> 1423, 1842\n142 <-> 29, 1766\n143 <-> 631, 1316\n144 <-> 201, 1547\n145 <-> 982, 1183, 1908\n146 <-> 921, 1094, 1619\n147 <-> 595\n148 <-> 515, 1008\n149 <-> 686\n150 <-> 1534, 1704, 1875\n151 <-> 996\n152 <-> 10, 1274\n153 <-> 1512\n154 <-> 117\n155 <-> 641\n156 <-> 185, 1794, 1804\n157 <-> 251\n158 <-> 874, 1992\n159 <-> 637\n160 <-> 160, 1057, 1429, 1902\n161 <-> 1355\n162 <-> 1347\n163 <-> 1286\n164 <-> 8, 343, 1636\n165 <-> 1078, 1098\n166 <-> 1325\n167 <-> 1900\n168 <-> 168\n169 <-> 169\n170 <-> 736, 1366\n171 <-> 171\n172 <-> 1860\n173 <-> 1874\n174 <-> 456\n175 <-> 487, 1165\n176 <-> 714, 1094, 1477, 1954\n177 <-> 330, 1799\n178 <-> 623, 975, 1849\n179 <-> 454\n180 <-> 1408, 1566\n181 <-> 181\n182 <-> 84, 220\n183 <-> 886, 1319, 1443, 1592\n184 <-> 983, 1231, 1496\n185 <-> 156, 276, 1686\n186 <-> 423, 1056\n187 <-> 1479\n188 <-> 612, 990\n189 <-> 391\n190 <-> 1188\n191 <-> 23, 191\n192 <-> 1419, 1671\n193 <-> 1825, 1847\n194 <-> 608, 899, 1629\n195 <-> 195, 1689, 1707\n196 <-> 1586\n197 <-> 314, 1983\n198 <-> 198, 595, 1267\n199 <-> 498, 1031, 1316\n200 <-> 905, 1266, 1385\n201 <-> 144, 1145\n202 <-> 250, 1089\n203 <-> 1462\n204 <-> 528, 1947\n205 <-> 205, 1460\n206 <-> 23\n207 <-> 305, 946\n208 <-> 919, 1829\n209 <-> 1352\n210 <-> 569\n211 <-> 1289\n212 <-> 493, 1286\n213 <-> 720\n214 <-> 214, 308, 1426, 1499\n215 <-> 518\n216 <-> 1129, 1895\n217 <-> 71, 608\n218 <-> 100, 664\n219 <-> 301, 876\n220 <-> 182, 754, 1040\n221 <-> 1439\n222 <-> 1466, 1533, 1852\n223 <-> 334, 1866\n224 <-> 320, 845, 864, 974\n225 <-> 1022, 1417\n226 <-> 1464, 1860\n227 <-> 651\n228 <-> 1187\n229 <-> 851\n230 <-> 230, 1120, 1576\n231 <-> 910\n232 <-> 453, 1015, 1498, 1547, 1884\n233 <-> 16, 712\n234 <-> 1167\n235 <-> 601, 670\n236 <-> 236\n237 <-> 1076, 1922\n238 <-> 39, 364, 1241, 1602\n239 <-> 632, 913\n240 <-> 975\n241 <-> 1431, 1819\n242 <-> 540\n243 <-> 741\n244 <-> 697, 1380, 1750, 1883\n245 <-> 1790\n246 <-> 698, 1791\n247 <-> 896\n248 <-> 248, 501\n249 <-> 513, 730, 1354\n250 <-> 202\n251 <-> 157, 251, 1719\n252 <-> 1421, 1904\n253 <-> 1190, 1820\n254 <-> 542\n255 <-> 132, 593\n256 <-> 1778\n257 <-> 1249, 1845\n258 <-> 572, 1134, 1847\n259 <-> 30, 1028, 1264\n260 <-> 546, 1270, 1841\n261 <-> 261\n262 <-> 746, 1068, 1258\n263 <-> 76, 885\n264 <-> 430, 1304\n265 <-> 469, 1046\n266 <-> 1511\n267 <-> 922, 1245\n268 <-> 1337\n269 <-> 785\n270 <-> 1219\n271 <-> 1051\n272 <-> 395, 1389, 1706\n273 <-> 1242, 1439\n274 <-> 1698\n275 <-> 1994\n276 <-> 41, 185, 1778\n277 <-> 1992\n278 <-> 340\n279 <-> 1739, 1783\n280 <-> 1817\n281 <-> 499\n282 <-> 74, 584\n283 <-> 316, 1020, 1612\n284 <-> 630, 917\n285 <-> 524\n286 <-> 614, 1446\n287 <-> 641\n288 <-> 1203\n289 <-> 1003, 1073\n290 <-> 1993\n291 <-> 957, 1042\n292 <-> 292\n293 <-> 825\n294 <-> 407, 712\n295 <-> 73, 733, 1878\n296 <-> 986, 1796\n297 <-> 1241\n298 <-> 1511\n299 <-> 467, 660, 1009\n300 <-> 1252\n301 <-> 219, 506, 1313\n302 <-> 478\n303 <-> 303, 586, 1656\n304 <-> 1724\n305 <-> 207\n306 <-> 904\n307 <-> 417, 1070\n308 <-> 214\n309 <-> 1402, 1971\n310 <-> 51, 371, 403, 794\n311 <-> 128, 516, 743\n312 <-> 602, 1328\n313 <-> 52, 1653\n314 <-> 197, 1070\n315 <-> 1990\n316 <-> 283, 1424\n317 <-> 1803\n318 <-> 1491, 1556\n319 <-> 982, 1533\n320 <-> 224\n321 <-> 401\n322 <-> 890\n323 <-> 1220, 1981\n324 <-> 324, 1849\n325 <-> 1153, 1206, 1573\n326 <-> 1645\n327 <-> 118, 857, 1064\n328 <-> 703, 1100\n329 <-> 1078, 1309\n330 <-> 177\n331 <-> 40, 1578, 1845\n332 <-> 332, 1096\n333 <-> 680, 1818, 1836\n334 <-> 223\n335 <-> 403\n336 <-> 404, 1239, 1858\n337 <-> 1406, 1610, 1788\n338 <-> 1405\n339 <-> 339\n340 <-> 278, 693, 1261, 1313\n341 <-> 816\n342 <-> 342\n343 <-> 164, 1569\n344 <-> 449\n345 <-> 772, 868\n346 <-> 754, 1722\n347 <-> 1073\n348 <-> 1658, 1916\n349 <-> 425, 725, 1757\n350 <-> 380, 963\n351 <-> 436, 507, 819, 966, 1603\n352 <-> 1464\n353 <-> 353, 1258\n354 <-> 354, 797\n355 <-> 1317\n356 <-> 1620, 1807\n357 <-> 648, 1202, 1708\n358 <-> 1529, 1703\n359 <-> 1305\n360 <-> 124, 842\n361 <-> 994, 1944\n362 <-> 362\n363 <-> 1221\n364 <-> 238, 1146, 1176\n365 <-> 509, 571\n366 <-> 6, 711, 1655\n367 <-> 137, 1953\n368 <-> 109\n369 <-> 369, 851, 863\n370 <-> 81\n371 <-> 310, 943\n372 <-> 927\n373 <-> 1953\n374 <-> 1823, 1828\n375 <-> 137, 1321\n376 <-> 376, 526, 721, 1359\n377 <-> 1647\n378 <-> 378, 686\n379 <-> 438, 651\n380 <-> 350, 883\n381 <-> 1171, 1772\n382 <-> 453\n383 <-> 1282\n384 <-> 1300\n385 <-> 1206, 1854\n386 <-> 386\n387 <-> 1962, 1978\n388 <-> 772\n389 <-> 622, 774, 1989\n390 <-> 459\n391 <-> 189, 688, 1351\n392 <-> 715, 910\n393 <-> 1924\n394 <-> 47, 1564\n395 <-> 272\n396 <-> 396, 1672\n397 <-> 1688\n398 <-> 398, 1648\n399 <-> 814\n400 <-> 1987\n401 <-> 321, 401\n402 <-> 56, 470, 1564, 1701\n403 <-> 310, 335\n404 <-> 336, 841, 1051\n405 <-> 936\n406 <-> 935\n407 <-> 294\n408 <-> 1507\n409 <-> 778\n410 <-> 1247\n411 <-> 1876, 1961, 1971\n412 <-> 0\n413 <-> 678, 1558\n414 <-> 38, 1687\n415 <-> 1474\n416 <-> 124, 702, 1006\n417 <-> 110, 307\n418 <-> 418\n419 <-> 1595\n420 <-> 689, 713\n421 <-> 1250, 1560\n422 <-> 1498\n423 <-> 186, 1824\n424 <-> 496\n425 <-> 349\n426 <-> 602\n427 <-> 493\n428 <-> 981, 1393, 1616, 1909\n429 <-> 1682\n430 <-> 264, 877\n431 <-> 1219, 1972\n432 <-> 1682\n433 <-> 1081, 1969\n434 <-> 121, 468, 1744\n435 <-> 1035, 1810\n436 <-> 351\n437 <-> 1950\n438 <-> 379, 1955\n439 <-> 439\n440 <-> 841\n441 <-> 1102, 1696\n442 <-> 682, 1502\n443 <-> 23, 1387\n444 <-> 1662, 1802\n445 <-> 1875\n446 <-> 563\n447 <-> 28\n448 <-> 568, 963, 1850\n449 <-> 344, 449\n450 <-> 588, 1003\n451 <-> 934, 1032\n452 <-> 7\n453 <-> 232, 382, 652, 1041, 1423, 1467\n454 <-> 179, 752\n455 <-> 1073, 1851\n456 <-> 91, 174, 726, 1610\n457 <-> 904, 1084, 1126\n458 <-> 1377, 1470, 1646\n459 <-> 390, 1244, 1478\n460 <-> 509, 1780\n461 <-> 1048, 1533\n462 <-> 485, 1941\n463 <-> 621, 1854\n464 <-> 1013, 1091, 1343, 1973\n465 <-> 1066\n466 <-> 1007\n467 <-> 299, 726\n468 <-> 434\n469 <-> 265, 1203\n470 <-> 402, 701, 1453\n471 <-> 753, 1085\n472 <-> 775, 1483, 1651, 1695, 1761\n473 <-> 514\n474 <-> 29, 99, 1025, 1756\n475 <-> 769, 799\n476 <-> 504, 779\n477 <-> 1310\n478 <-> 302, 1939\n479 <-> 950, 1278\n480 <-> 0\n481 <-> 1805\n482 <-> 482, 1837\n483 <-> 483\n484 <-> 484\n485 <-> 462, 485, 1293\n486 <-> 509\n487 <-> 175, 1124, 1772, 1884, 1919\n488 <-> 1907\n489 <-> 489\n490 <-> 624, 1151\n491 <-> 72, 579\n492 <-> 492\n493 <-> 212, 427, 853, 884\n494 <-> 138, 1381, 1916\n495 <-> 25, 944\n496 <-> 424, 1749\n497 <-> 793, 1767, 1942\n498 <-> 199\n499 <-> 281, 1177, 1917\n500 <-> 1049\n501 <-> 248\n502 <-> 110, 676\n503 <-> 1436, 1513\n504 <-> 476\n505 <-> 569, 1416\n506 <-> 18, 301, 648\n507 <-> 351, 881\n508 <-> 95, 1313\n509 <-> 365, 460, 486\n510 <-> 604\n511 <-> 1526\n512 <-> 126, 1394, 1434\n513 <-> 249, 951, 1809\n514 <-> 473, 1106\n515 <-> 148, 906, 1950\n516 <-> 311, 1079\n517 <-> 709\n518 <-> 215, 1483\n519 <-> 1451, 1692\n520 <-> 816, 1937\n521 <-> 521\n522 <-> 935, 1154\n523 <-> 971, 1197, 1737\n524 <-> 285, 796, 1472\n525 <-> 1001, 1033, 1756\n526 <-> 376, 1736\n527 <-> 1311, 1785\n528 <-> 5, 204\n529 <-> 1541, 1864, 1879\n530 <-> 1052\n531 <-> 647, 1890\n532 <-> 780, 1597\n533 <-> 1258\n534 <-> 1231, 1963\n535 <-> 1637\n536 <-> 124\n537 <-> 1633\n538 <-> 538\n539 <-> 843\n540 <-> 242, 1522\n541 <-> 1644\n542 <-> 64, 254, 1623\n543 <-> 580, 1484\n544 <-> 1214, 1996\n545 <-> 1959\n546 <-> 260, 1765\n547 <-> 1335\n548 <-> 977\n549 <-> 1384\n550 <-> 901, 956\n551 <-> 1681, 1830\n552 <-> 29\n553 <-> 1608\n554 <-> 637\n555 <-> 1743\n556 <-> 1118, 1868\n557 <-> 1278, 1289\n558 <-> 994, 1095\n559 <-> 1151, 1376\n560 <-> 1224, 1758\n561 <-> 1720\n562 <-> 562\n563 <-> 446, 563\n564 <-> 1173, 1985\n565 <-> 960, 1300, 1517\n566 <-> 984, 1583\n567 <-> 871, 1294, 1609\n568 <-> 448, 1487\n569 <-> 210, 505\n570 <-> 888, 1042\n571 <-> 365\n572 <-> 26, 258, 572\n573 <-> 913\n574 <-> 1614\n575 <-> 658, 1404\n576 <-> 837\n577 <-> 1060\n578 <-> 693\n579 <-> 491\n580 <-> 543, 1192\n581 <-> 928\n582 <-> 943, 1494\n583 <-> 1086, 1193, 1209\n584 <-> 282, 835\n585 <-> 1095\n586 <-> 303\n587 <-> 1726\n588 <-> 450, 1430, 1797, 1881\n589 <-> 133, 1231\n590 <-> 1996\n591 <-> 51, 1104\n592 <-> 592\n593 <-> 255, 821\n594 <-> 1097, 1260\n595 <-> 147, 198, 612, 1940\n596 <-> 1150\n597 <-> 77\n598 <-> 674\n599 <-> 1978\n600 <-> 773, 1332\n601 <-> 235\n602 <-> 59, 312, 426, 1088, 1745\n603 <-> 1031, 1898\n604 <-> 510, 1062\n605 <-> 1072\n606 <-> 606, 672, 1072\n607 <-> 1090, 1198, 1749\n608 <-> 194, 217\n609 <-> 609, 1121\n610 <-> 1858\n611 <-> 1351\n612 <-> 188, 595, 679\n613 <-> 1533\n614 <-> 286, 1283, 1888\n615 <-> 1225\n616 <-> 616\n617 <-> 93, 1566\n618 <-> 1694\n619 <-> 1674\n620 <-> 131, 889, 1045, 1107\n621 <-> 463, 1295\n622 <-> 389\n623 <-> 178\n624 <-> 490, 1233, 1473\n625 <-> 1601\n626 <-> 766, 1515\n627 <-> 1747\n628 <-> 1176\n629 <-> 840\n630 <-> 284, 743\n631 <-> 41, 143\n632 <-> 239, 742\n633 <-> 1265, 1792\n634 <-> 634\n635 <-> 811, 970\n636 <-> 1207, 1568\n637 <-> 159, 554, 978\n638 <-> 665, 1699, 1822\n639 <-> 980, 1442\n640 <-> 65, 783, 1817\n641 <-> 155, 287, 641, 1259\n642 <-> 709, 745, 892, 1766, 1798\n643 <-> 1998\n644 <-> 1006, 1749\n645 <-> 1179, 1274\n646 <-> 1284\n647 <-> 531, 647, 904\n648 <-> 55, 357, 506, 1395\n649 <-> 971, 1910\n650 <-> 38\n651 <-> 69, 227, 379, 1755\n652 <-> 453, 1935\n653 <-> 33\n654 <-> 1630, 1887\n655 <-> 1792\n656 <-> 1504\n657 <-> 1205, 1824\n658 <-> 575\n659 <-> 1805\n660 <-> 299\n661 <-> 924\n662 <-> 47, 846\n663 <-> 860, 1568\n664 <-> 218\n665 <-> 65, 638, 1208, 1287\n666 <-> 37, 86, 1792\n667 <-> 1176\n668 <-> 1056\n669 <-> 1453, 1933\n670 <-> 235, 747, 1410\n671 <-> 671, 1545\n672 <-> 606, 1640\n673 <-> 1615\n674 <-> 598, 1727\n675 <-> 102, 1560\n676 <-> 502\n677 <-> 1479\n678 <-> 413, 1510\n679 <-> 612, 1591, 1938\n680 <-> 333, 1010, 1264, 1835\n681 <-> 891\n682 <-> 442, 1872\n683 <-> 61, 933, 987\n684 <-> 684, 867\n685 <-> 1467\n686 <-> 149, 378\n687 <-> 1222\n688 <-> 391, 1833\n689 <-> 420, 829\n690 <-> 1920, 1950\n691 <-> 83, 1030\n692 <-> 812\n693 <-> 340, 578\n694 <-> 760, 1197\n695 <-> 849, 1946\n696 <-> 696\n697 <-> 244, 697, 859\n698 <-> 246, 1398\n699 <-> 1240, 1483\n700 <-> 1652\n701 <-> 7, 470, 1761\n702 <-> 416, 1707\n703 <-> 328, 1745\n704 <-> 704, 811, 860\n705 <-> 705\n706 <-> 706, 1584\n707 <-> 115, 904, 1523\n708 <-> 1306\n709 <-> 517, 642\n710 <-> 75\n711 <-> 366, 1932\n712 <-> 233, 294, 1486\n713 <-> 420\n714 <-> 176, 929, 1103, 1748\n715 <-> 392, 1800\n716 <-> 824\n717 <-> 1527, 1845\n718 <-> 129\n719 <-> 1824\n720 <-> 213, 720\n721 <-> 376\n722 <-> 773, 1093, 1659\n723 <-> 723\n724 <-> 724, 999, 1831\n725 <-> 349, 1965\n726 <-> 456, 467\n727 <-> 727, 1855\n728 <-> 728\n729 <-> 134\n730 <-> 249\n731 <-> 58\n732 <-> 799, 1386\n733 <-> 295\n734 <-> 1976\n735 <-> 735\n736 <-> 170\n737 <-> 1795\n738 <-> 1852\n739 <-> 1457, 1487, 1504\n740 <-> 923\n741 <-> 243, 1039\n742 <-> 632\n743 <-> 311, 630\n744 <-> 1837\n745 <-> 642\n746 <-> 262, 1059, 1308\n747 <-> 670, 1218\n748 <-> 898\n749 <-> 1904\n750 <-> 1997\n751 <-> 917, 990, 1588\n752 <-> 454, 916\n753 <-> 471\n754 <-> 220, 346, 1661\n755 <-> 1550\n756 <-> 22, 1521\n757 <-> 1540\n758 <-> 862, 1575\n759 <-> 759, 1118, 1561, 1966\n760 <-> 694, 760\n761 <-> 66\n762 <-> 1080, 1817\n763 <-> 763, 1872\n764 <-> 817\n765 <-> 765\n766 <-> 626, 905\n767 <-> 113, 856, 1563, 1905\n768 <-> 1308, 1674\n769 <-> 475, 1009, 1510\n770 <-> 770\n771 <-> 771, 1893\n772 <-> 345, 388\n773 <-> 600, 722\n774 <-> 389, 990, 1254\n775 <-> 472\n776 <-> 1473\n777 <-> 0\n778 <-> 409, 854, 1244\n779 <-> 52, 476, 1691, 1761\n780 <-> 532\n781 <-> 1631\n782 <-> 67, 1043\n783 <-> 640\n784 <-> 896\n785 <-> 269, 1383, 1992\n786 <-> 1095\n787 <-> 914, 975\n788 <-> 1674\n789 <-> 1593\n790 <-> 113\n791 <-> 1983\n792 <-> 1136\n793 <-> 13, 497, 995, 1738\n794 <-> 310\n795 <-> 810\n796 <-> 524, 1342\n797 <-> 354, 1713\n798 <-> 1164\n799 <-> 475, 732\n800 <-> 46, 1448\n801 <-> 830, 909, 1471, 1829\n802 <-> 1019, 1509\n803 <-> 62\n804 <-> 1934\n805 <-> 1052\n806 <-> 1356, 1647\n807 <-> 807\n808 <-> 808\n809 <-> 1130, 1895\n810 <-> 795, 810, 1555\n811 <-> 635, 704, 1417\n812 <-> 692, 1831\n813 <-> 1335, 1708\n814 <-> 399, 873, 1256\n815 <-> 1818\n816 <-> 341, 520\n817 <-> 764, 903\n818 <-> 1061\n819 <-> 351, 1077\n820 <-> 1885\n821 <-> 593\n822 <-> 1590, 1679, 1757\n823 <-> 1034, 1860\n824 <-> 716, 1879\n825 <-> 293, 1276, 1619, 1877\n826 <-> 978\n827 <-> 1778\n828 <-> 1263, 1317\n829 <-> 689, 1037, 1585\n830 <-> 801\n831 <-> 1551, 1998\n832 <-> 104\n833 <-> 1194, 1925\n834 <-> 900, 1924\n835 <-> 584\n836 <-> 1196, 1679\n837 <-> 576, 1253\n838 <-> 1484, 1543\n839 <-> 1904\n840 <-> 31, 629, 1136, 1750\n841 <-> 122, 404, 440\n842 <-> 35, 360, 1859\n843 <-> 539, 1303, 1368, 1639\n844 <-> 1388\n845 <-> 224, 1018, 1205, 1314\n846 <-> 77, 662\n847 <-> 1969\n848 <-> 1437\n849 <-> 695, 1698\n850 <-> 850\n851 <-> 229, 369\n852 <-> 50\n853 <-> 493, 895, 1951\n854 <-> 778, 1243, 1385\n855 <-> 855\n856 <-> 34, 767\n857 <-> 327, 1890\n858 <-> 858, 1301\n859 <-> 697, 1227, 1454\n860 <-> 663, 704, 1076\n861 <-> 87, 1721\n862 <-> 758, 870\n863 <-> 369, 911\n864 <-> 224, 1000\n865 <-> 110\n866 <-> 1976\n867 <-> 684\n868 <-> 345, 1985\n869 <-> 1058\n870 <-> 862, 1867\n871 <-> 567\n872 <-> 43, 1173, 1369\n873 <-> 814\n874 <-> 158\n875 <-> 1163, 1592\n876 <-> 219\n877 <-> 430, 1108\n878 <-> 897, 1196\n879 <-> 1475\n880 <-> 78\n881 <-> 507, 1842\n882 <-> 44\n883 <-> 380\n884 <-> 493\n885 <-> 263\n886 <-> 183\n887 <-> 1387\n888 <-> 570, 1306\n889 <-> 620\n890 <-> 322, 1987\n891 <-> 681, 1619\n892 <-> 642, 1122, 1762\n893 <-> 893\n894 <-> 1163\n895 <-> 853\n896 <-> 247, 784, 1073, 1400\n897 <-> 878\n898 <-> 748, 919\n899 <-> 194\n900 <-> 834, 1298, 1412\n901 <-> 550, 1187, 1476\n902 <-> 902, 918\n903 <-> 817, 1410\n904 <-> 306, 457, 647, 707, 1942\n905 <-> 200, 766\n906 <-> 515\n907 <-> 1440, 1680\n908 <-> 1738\n909 <-> 801\n910 <-> 231, 392, 1690, 1890\n911 <-> 863, 1215\n912 <-> 9, 912\n913 <-> 239, 573, 1058\n914 <-> 787, 1098\n915 <-> 922\n916 <-> 752, 916\n917 <-> 284, 751, 1149, 1221\n918 <-> 902\n919 <-> 208, 898, 1225, 1456\n920 <-> 9, 27, 51\n921 <-> 146, 921\n922 <-> 53, 267, 915\n923 <-> 22, 740, 1356\n924 <-> 48, 661\n925 <-> 1105, 1366\n926 <-> 57, 1577\n927 <-> 372, 1101, 1669, 1783\n928 <-> 85, 581, 928, 949, 1490, 1801\n929 <-> 714, 1463\n930 <-> 122\n931 <-> 1349\n932 <-> 934\n933 <-> 683\n934 <-> 451, 932, 1986\n935 <-> 406, 522, 1137, 1263\n936 <-> 405, 1401, 1603, 1822\n937 <-> 1321\n938 <-> 1469\n939 <-> 939\n940 <-> 1111\n941 <-> 109\n942 <-> 942, 1637\n943 <-> 371, 582\n944 <-> 495, 1882\n945 <-> 1634\n946 <-> 125, 207, 946\n947 <-> 947\n948 <-> 1211\n949 <-> 928\n950 <-> 105, 479\n951 <-> 513, 1491\n952 <-> 952, 1199\n953 <-> 42\n954 <-> 1214, 1782\n955 <-> 1241, 1772, 1970\n956 <-> 550\n957 <-> 291, 990\n958 <-> 1785, 1856\n959 <-> 968, 1186, 1559, 1827\n960 <-> 565\n961 <-> 124\n962 <-> 1701\n963 <-> 350, 448\n964 <-> 74, 1066, 1452\n965 <-> 64, 1342\n966 <-> 351\n967 <-> 1193, 1300, 1563\n968 <-> 959\n969 <-> 1824\n970 <-> 635, 1636\n971 <-> 523, 649\n972 <-> 977, 1781, 1799\n973 <-> 1735\n974 <-> 224\n975 <-> 178, 240, 787, 1440\n976 <-> 1004\n977 <-> 548, 972, 977, 1345\n978 <-> 637, 826, 1307, 1508\n979 <-> 1103\n980 <-> 45, 639\n981 <-> 428\n982 <-> 145, 319\n983 <-> 78, 184\n984 <-> 566, 984\n985 <-> 1573\n986 <-> 296\n987 <-> 683\n988 <-> 988\n989 <-> 1219, 1586\n990 <-> 188, 751, 774, 957\n991 <-> 1093, 1191, 1613\n992 <-> 1531\n993 <-> 1698\n994 <-> 361, 558, 1339, 1903\n995 <-> 98, 793\n996 <-> 151, 1101, 1886\n997 <-> 78\n998 <-> 107\n999 <-> 724, 1951\n1000 <-> 864, 1058\n1001 <-> 66, 525\n1002 <-> 134\n1003 <-> 289, 450, 1635\n1004 <-> 976, 1340, 1452\n1005 <-> 1178, 1776, 1881\n1006 <-> 416, 644\n1007 <-> 58, 466, 1375, 1835\n1008 <-> 106, 148, 1524\n1009 <-> 299, 769\n1010 <-> 680, 1667\n1011 <-> 1011\n1012 <-> 63\n1013 <-> 103, 464\n1014 <-> 1134, 1779\n1015 <-> 232\n1016 <-> 1016\n1017 <-> 1851\n1018 <-> 100, 845, 1493\n1019 <-> 802, 1604\n1020 <-> 283\n1021 <-> 1175, 1540, 1553\n1022 <-> 225\n1023 <-> 80, 1286, 1878\n1024 <-> 1562\n1025 <-> 474\n1026 <-> 1026\n1027 <-> 76, 1443, 1899\n1028 <-> 259\n1029 <-> 1798\n1030 <-> 691\n1031 <-> 199, 603, 1585, 1734\n1032 <-> 451\n1033 <-> 525, 1416\n1034 <-> 823, 1117, 1657\n1035 <-> 435, 1826\n1036 <-> 1640\n1037 <-> 829, 1654\n1038 <-> 1692\n1039 <-> 741, 1612, 1780\n1040 <-> 220\n1041 <-> 453\n1042 <-> 291, 570\n1043 <-> 782\n1044 <-> 1044, 1508, 1897, 1930\n1045 <-> 620, 1045, 1052\n1046 <-> 265\n1047 <-> 1565, 1718\n1048 <-> 461\n1049 <-> 500, 1827\n1050 <-> 1050, 1729\n1051 <-> 271, 404\n1052 <-> 530, 805, 1045\n1053 <-> 1335, 1642\n1054 <-> 33, 1057\n1055 <-> 1055\n1056 <-> 186, 668, 1110, 1113\n1057 <-> 160, 1054, 1278\n1058 <-> 869, 913, 1000\n1059 <-> 746\n1060 <-> 577, 1124\n1061 <-> 818, 1536, 1894\n1062 <-> 118, 604\n1063 <-> 1125\n1064 <-> 327, 1318\n1065 <-> 87, 1728\n1066 <-> 465, 964, 1685\n1067 <-> 1067, 1796\n1068 <-> 262\n1069 <-> 1304, 1632\n1070 <-> 307, 314, 1906\n1071 <-> 1650\n1072 <-> 605, 606\n1073 <-> 289, 347, 455, 896, 1132\n1074 <-> 1245\n1075 <-> 75\n1076 <-> 237, 860\n1077 <-> 819\n1078 <-> 165, 329\n1079 <-> 516\n1080 <-> 762\n1081 <-> 433, 1182\n1082 <-> 140, 1597\n1083 <-> 1977\n1084 <-> 457\n1085 <-> 471, 1933\n1086 <-> 583, 1752, 1923\n1087 <-> 1101\n1088 <-> 120, 602\n1089 <-> 29, 202, 1238\n1090 <-> 607, 1773, 1982\n1091 <-> 464, 1590, 1918\n1092 <-> 1580, 1880\n1093 <-> 722, 991\n1094 <-> 146, 176\n1095 <-> 558, 585, 786, 1217\n1096 <-> 42, 332\n1097 <-> 594\n1098 <-> 165, 914\n1099 <-> 1672\n1100 <-> 328, 1998\n1101 <-> 927, 996, 1087, 1234, 1994\n1102 <-> 441, 1939\n1103 <-> 714, 979, 1298\n1104 <-> 591\n1105 <-> 925\n1106 <-> 514, 1697\n1107 <-> 620, 1485\n1108 <-> 877, 1108\n1109 <-> 11, 1325, 1355, 1627, 1733\n1110 <-> 1056, 1409, 1896\n1111 <-> 940, 1210\n1112 <-> 1112\n1113 <-> 1056\n1114 <-> 1291, 1595\n1115 <-> 91\n1116 <-> 1336\n1117 <-> 1034, 1528\n1118 <-> 556, 759\n1119 <-> 1329\n1120 <-> 81, 230\n1121 <-> 609, 1326\n1122 <-> 892\n1123 <-> 1500\n1124 <-> 487, 1060\n1125 <-> 1063, 1230\n1126 <-> 457\n1127 <-> 27\n1128 <-> 1763\n1129 <-> 58, 216, 1642\n1130 <-> 809\n1131 <-> 127, 1189, 1353\n1132 <-> 1073\n1133 <-> 1685\n1134 <-> 258, 1014, 1503\n1135 <-> 136\n1136 <-> 792, 840\n1137 <-> 935\n1138 <-> 130\n1139 <-> 1505, 1915\n1140 <-> 1759\n1141 <-> 1141, 1937\n1142 <-> 1539\n1143 <-> 1640\n1144 <-> 1144, 1468\n1145 <-> 201, 1272, 1488\n1146 <-> 4, 364\n1147 <-> 1271, 1446\n1148 <-> 6, 1593\n1149 <-> 917\n1150 <-> 596, 1760\n1151 <-> 490, 559\n1152 <-> 1530, 1834\n1153 <-> 325, 1885\n1154 <-> 522, 1620, 1770\n1155 <-> 1417\n1156 <-> 1380, 1397\n1157 <-> 1829\n1158 <-> 1158\n1159 <-> 60, 1787\n1160 <-> 1823\n1161 <-> 1278, 1710, 1948\n1162 <-> 1319, 1999\n1163 <-> 875, 894\n1164 <-> 798, 1902\n1165 <-> 175\n1166 <-> 1166\n1167 <-> 92, 234\n1168 <-> 1652\n1169 <-> 57, 1358\n1170 <-> 1334\n1171 <-> 381\n1172 <-> 36, 1449, 1661\n1173 <-> 564, 872\n1174 <-> 1884\n1175 <-> 1021, 1717, 1759\n1176 <-> 364, 628, 667, 1420, 1641\n1177 <-> 499, 1374, 1405, 1931\n1178 <-> 1005\n1179 <-> 645\n1180 <-> 1302, 1634\n1181 <-> 1654\n1182 <-> 1081, 1460, 1700\n1183 <-> 145\n1184 <-> 1975\n1185 <-> 34\n1186 <-> 959, 1790\n1187 <-> 228, 901, 1628\n1188 <-> 190, 1706\n1189 <-> 1131\n1190 <-> 253\n1191 <-> 991\n1192 <-> 580, 1429\n1193 <-> 583, 967\n1194 <-> 75, 833, 1214\n1195 <-> 1445, 1454\n1196 <-> 836, 878\n1197 <-> 523, 694\n1198 <-> 607\n1199 <-> 952\n1200 <-> 1624, 1840\n1201 <-> 127, 1201, 1330\n1202 <-> 357, 1404\n1203 <-> 288, 469, 1461\n1204 <-> 1559\n1205 <-> 657, 845\n1206 <-> 325, 385\n1207 <-> 636, 1362, 1873\n1208 <-> 665\n1209 <-> 1, 583\n1210 <-> 1111, 1669\n1211 <-> 948, 1753\n1212 <-> 1228\n1213 <-> 1361, 1626\n1214 <-> 544, 954, 1194, 1582\n1215 <-> 911\n1216 <-> 1765\n1217 <-> 1095\n1218 <-> 747, 1484\n1219 <-> 270, 431, 989, 1465, 1475\n1220 <-> 323, 1220\n1221 <-> 363, 917\n1222 <-> 122, 687, 1622\n1223 <-> 1223\n1224 <-> 31, 560\n1225 <-> 615, 919\n1226 <-> 1582, 1678\n1227 <-> 859\n1228 <-> 1212, 1357\n1229 <-> 48\n1230 <-> 1125, 1927\n1231 <-> 184, 534, 589\n1232 <-> 62\n1233 <-> 624\n1234 <-> 1101\n1235 <-> 1235\n1236 <-> 1236, 1424\n1237 <-> 1984\n1238 <-> 1089, 1829, 1980\n1239 <-> 336, 1634\n1240 <-> 699\n1241 <-> 238, 297, 955\n1242 <-> 273\n1243 <-> 854, 1581, 1702\n1244 <-> 459, 778, 1853\n1245 <-> 267, 1074\n1246 <-> 1850\n1247 <-> 36, 410\n1248 <-> 1489\n1249 <-> 257, 1752\n1250 <-> 421\n1251 <-> 1630\n1252 <-> 300, 1380, 1803\n1253 <-> 837, 1464, 1901\n1254 <-> 774\n1255 <-> 1283\n1256 <-> 814, 1771, 1821\n1257 <-> 1276\n1258 <-> 262, 353, 533, 1465\n1259 <-> 641\n1260 <-> 95, 594\n1261 <-> 340\n1262 <-> 1262\n1263 <-> 828, 935\n1264 <-> 259, 680\n1265 <-> 633, 1666\n1266 <-> 200\n1267 <-> 198\n1268 <-> 1965\n1269 <-> 1805, 1851\n1270 <-> 260, 1270\n1271 <-> 1147\n1272 <-> 1145, 1667\n1273 <-> 1316\n1274 <-> 44, 86, 152, 645, 1900\n1275 <-> 132\n1276 <-> 825, 1257\n1277 <-> 1277\n1278 <-> 479, 557, 1057, 1161\n1279 <-> 1279\n1280 <-> 1280, 1863\n1281 <-> 1845\n1282 <-> 12, 383, 1839\n1283 <-> 614, 1255\n1284 <-> 646, 1481\n1285 <-> 1285\n1286 <-> 163, 212, 1023\n1287 <-> 665\n1288 <-> 1288\n1289 <-> 211, 557, 1991\n1290 <-> 1919\n1291 <-> 1114\n1292 <-> 1817\n1293 <-> 485, 1537, 1631\n1294 <-> 567\n1295 <-> 621\n1296 <-> 1439, 1664\n1297 <-> 16\n1298 <-> 900, 1103\n1299 <-> 1754\n1300 <-> 384, 565, 967\n1301 <-> 858, 1683, 1703\n1302 <-> 1180, 1302\n1303 <-> 843\n1304 <-> 28, 264, 1069\n1305 <-> 90, 359, 1385\n1306 <-> 708, 888\n1307 <-> 978, 1506, 1728\n1308 <-> 746, 768\n1309 <-> 329, 1715\n1310 <-> 86, 477, 1634\n1311 <-> 527, 1675\n1312 <-> 81\n1313 <-> 301, 340, 508\n1314 <-> 845, 1314\n1315 <-> 1531\n1316 <-> 143, 199, 1273, 1379, 1684\n1317 <-> 355, 828, 1635, 1697\n1318 <-> 1064\n1319 <-> 183, 1162, 1732, 1754\n1320 <-> 1320\n1321 <-> 375, 937, 1926\n1322 <-> 1336\n1323 <-> 1494, 1820\n1324 <-> 1324\n1325 <-> 166, 1109\n1326 <-> 1121\n1327 <-> 1753, 1993\n1328 <-> 312, 1512\n1329 <-> 1119, 1329\n1330 <-> 1201\n1331 <-> 1851\n1332 <-> 600\n1333 <-> 1376, 1869\n1334 <-> 1170, 1859\n1335 <-> 101, 547, 813, 1053\n1336 <-> 1116, 1322, 1667\n1337 <-> 268, 1946\n1338 <-> 1514\n1339 <-> 994, 1562\n1340 <-> 1004, 1340, 1444\n1341 <-> 1623\n1342 <-> 796, 965, 1342\n1343 <-> 464\n1344 <-> 39\n1345 <-> 977\n1346 <-> 1609, 1802\n1347 <-> 114, 162\n1348 <-> 62, 1917\n1349 <-> 931, 1349, 1963\n1350 <-> 1350, 1378\n1351 <-> 391, 611, 1351, 1985\n1352 <-> 209, 1352\n1353 <-> 1131\n1354 <-> 249\n1355 <-> 161, 1109, 1607\n1356 <-> 806, 923, 1905, 1911\n1357 <-> 1228, 1915\n1358 <-> 1169\n1359 <-> 376, 1815\n1360 <-> 1631, 1914\n1361 <-> 1213\n1362 <-> 1207\n1363 <-> 1733\n1364 <-> 1596\n1365 <-> 1763\n1366 <-> 170, 925, 1750\n1367 <-> 113\n1368 <-> 102, 843\n1369 <-> 872, 1959\n1370 <-> 1370\n1371 <-> 1371\n1372 <-> 46\n1373 <-> 1420\n1374 <-> 1177, 1374\n1375 <-> 1007\n1376 <-> 559, 1333, 1977\n1377 <-> 458, 1986\n1378 <-> 1350\n1379 <-> 1316\n1380 <-> 244, 1156, 1252\n1381 <-> 494\n1382 <-> 1447\n1383 <-> 785\n1384 <-> 549, 1384\n1385 <-> 200, 854, 1305\n1386 <-> 732\n1387 <-> 443, 887\n1388 <-> 844, 1723, 1958\n1389 <-> 272, 1914\n1390 <-> 1487, 1806\n1391 <-> 1523\n1392 <-> 1746, 1872\n1393 <-> 428\n1394 <-> 512\n1395 <-> 648\n1396 <-> 92, 1537, 1663\n1397 <-> 1156\n1398 <-> 79, 698, 1433, 1497\n1399 <-> 1399\n1400 <-> 896\n1401 <-> 936\n1402 <-> 309\n1403 <-> 1795, 1877\n1404 <-> 575, 1202, 1741\n1405 <-> 338, 1177\n1406 <-> 337\n1407 <-> 1824\n1408 <-> 180, 1570, 1769\n1409 <-> 1110\n1410 <-> 670, 903\n1411 <-> 75\n1412 <-> 900\n1413 <-> 15\n1414 <-> 1545\n1415 <-> 1415\n1416 <-> 505, 1033\n1417 <-> 225, 811, 1155\n1418 <-> 1996\n1419 <-> 192\n1420 <-> 1176, 1373, 1489, 1577\n1421 <-> 114, 252, 1928\n1422 <-> 1995\n1423 <-> 141, 453\n1424 <-> 316, 1236\n1425 <-> 1774, 1775\n1426 <-> 214, 1437\n1427 <-> 1901\n1428 <-> 1990\n1429 <-> 160, 1192\n1430 <-> 588\n1431 <-> 117, 241, 1818\n1432 <-> 1432\n1433 <-> 1398\n1434 <-> 512\n1435 <-> 1660\n1436 <-> 503, 1436, 1952\n1437 <-> 848, 1426\n1438 <-> 1660, 1769\n1439 <-> 221, 273, 1296\n1440 <-> 907, 975\n1441 <-> 1607\n1442 <-> 47, 639\n1443 <-> 183, 1027, 1915\n1444 <-> 1340\n1445 <-> 1195\n1446 <-> 286, 1147, 1518\n1447 <-> 1382, 1588\n1448 <-> 800, 1480, 1891\n1449 <-> 1172\n1450 <-> 1450, 1811\n1451 <-> 519, 1823\n1452 <-> 964, 1004\n1453 <-> 0, 470, 669\n1454 <-> 859, 1195\n1455 <-> 125, 1473\n1456 <-> 919\n1457 <-> 739, 1556\n1458 <-> 90\n1459 <-> 111, 1459\n1460 <-> 205, 1182\n1461 <-> 63, 119, 1203, 1461\n1462 <-> 203, 1978\n1463 <-> 929\n1464 <-> 226, 352, 1253\n1465 <-> 1219, 1258\n1466 <-> 222\n1467 <-> 453, 685, 1936\n1468 <-> 1144, 1843\n1469 <-> 938, 1469\n1470 <-> 458\n1471 <-> 801\n1472 <-> 524\n1473 <-> 624, 776, 1455\n1474 <-> 415, 1716\n1475 <-> 879, 1219, 1760\n1476 <-> 901, 1476\n1477 <-> 176\n1478 <-> 459\n1479 <-> 86, 187, 677\n1480 <-> 1448, 1783\n1481 <-> 1284, 1674\n1482 <-> 1528, 1711\n1483 <-> 472, 518, 699\n1484 <-> 543, 838, 1218, 1645\n1485 <-> 1107\n1486 <-> 712, 1486, 1574\n1487 <-> 568, 739, 1390\n1488 <-> 1145, 1862\n1489 <-> 1248, 1420\n1490 <-> 928\n1491 <-> 318, 951\n1492 <-> 1492\n1493 <-> 1018, 1856, 1907\n1494 <-> 582, 1323, 1892\n1495 <-> 1573\n1496 <-> 184, 1846\n1497 <-> 1398\n1498 <-> 124, 232, 422\n1499 <-> 214\n1500 <-> 1123, 1747\n1501 <-> 140, 1501\n1502 <-> 442\n1503 <-> 1134\n1504 <-> 656, 739\n1505 <-> 1139\n1506 <-> 1307\n1507 <-> 408, 1903\n1508 <-> 978, 1044, 1512\n1509 <-> 802, 1700\n1510 <-> 678, 769, 1641, 1865\n1511 <-> 266, 298, 1587\n1512 <-> 153, 1328, 1508\n1513 <-> 503, 1747, 1976\n1514 <-> 1338, 1590\n1515 <-> 626\n1516 <-> 1519\n1517 <-> 40, 565, 1743, 1787\n1518 <-> 1446\n1519 <-> 1516, 1519\n1520 <-> 1538, 1599\n1521 <-> 756, 1988, 1993\n1522 <-> 540, 1644, 1669\n1523 <-> 707, 1391\n1524 <-> 1008\n1525 <-> 1659\n1526 <-> 20, 511, 1706\n1527 <-> 717, 1598\n1528 <-> 1117, 1482, 1528, 1596\n1529 <-> 358\n1530 <-> 1152, 1606\n1531 <-> 90, 992, 1315, 1914\n1532 <-> 1532\n1533 <-> 222, 319, 461, 613, 1828\n1534 <-> 150\n1535 <-> 1535\n1536 <-> 1061\n1537 <-> 1293, 1396, 1652\n1538 <-> 1520, 1538, 1789\n1539 <-> 1142, 1681, 1689\n1540 <-> 757, 1021\n1541 <-> 529, 1554\n1542 <-> 1639, 1784\n1543 <-> 838\n1544 <-> 1544\n1545 <-> 671, 1414\n1546 <-> 1577, 1709\n1547 <-> 144, 232\n1548 <-> 1548\n1549 <-> 1727, 1783, 1871\n1550 <-> 755, 1812\n1551 <-> 831\n1552 <-> 1552\n1553 <-> 1021\n1554 <-> 1541\n1555 <-> 810\n1556 <-> 318, 1457\n1557 <-> 1557, 1625\n1558 <-> 413, 1921\n1559 <-> 959, 1204\n1560 <-> 421, 675\n1561 <-> 759, 1808\n1562 <-> 1024, 1339\n1563 <-> 767, 967\n1564 <-> 394, 402\n1565 <-> 1047, 1565\n1566 <-> 180, 617, 1605\n1567 <-> 1567\n1568 <-> 636, 663\n1569 <-> 343\n1570 <-> 1408, 1705\n1571 <-> 1688\n1572 <-> 1908, 1929\n1573 <-> 325, 985, 1495, 1769\n1574 <-> 1486\n1575 <-> 758\n1576 <-> 230\n1577 <-> 926, 1420, 1546\n1578 <-> 331\n1579 <-> 1697\n1580 <-> 1092, 1881\n1581 <-> 1243\n1582 <-> 1214, 1226\n1583 <-> 566\n1584 <-> 706\n1585 <-> 829, 1031\n1586 <-> 196, 989, 1960\n1587 <-> 1511, 1630, 1649\n1588 <-> 88, 751, 1447\n1589 <-> 98\n1590 <-> 822, 1091, 1514, 1882\n1591 <-> 679\n1592 <-> 183, 875\n1593 <-> 789, 1148\n1594 <-> 1986\n1595 <-> 87, 419, 1114\n1596 <-> 1364, 1528\n1597 <-> 532, 1082\n1598 <-> 1527, 1633\n1599 <-> 1520\n1600 <-> 45\n1601 <-> 625, 1652\n1602 <-> 238\n1603 <-> 83, 351, 936, 1605\n1604 <-> 1019, 1944\n1605 <-> 1566, 1603\n1606 <-> 37, 1530\n1607 <-> 1355, 1441, 1617\n1608 <-> 553, 1608\n1609 <-> 567, 1346\n1610 <-> 337, 456\n1611 <-> 1910\n1612 <-> 283, 1039\n1613 <-> 991\n1614 <-> 2, 574, 1614\n1615 <-> 673, 1827\n1616 <-> 428\n1617 <-> 1607, 1617\n1618 <-> 1691, 1770\n1619 <-> 146, 825, 891\n1620 <-> 356, 1154\n1621 <-> 1637\n1622 <-> 96, 1222\n1623 <-> 542, 1341\n1624 <-> 1200, 1796\n1625 <-> 1557\n1626 <-> 1213, 1626\n1627 <-> 1109\n1628 <-> 1187\n1629 <-> 58, 194\n1630 <-> 654, 1251, 1587\n1631 <-> 781, 1293, 1360\n1632 <-> 1069\n1633 <-> 537, 1598\n1634 <-> 945, 1180, 1239, 1310\n1635 <-> 1003, 1317\n1636 <-> 164, 970\n1637 <-> 535, 942, 1621\n1638 <-> 1643\n1639 <-> 843, 1542, 1753\n1640 <-> 672, 1036, 1143\n1641 <-> 1176, 1510\n1642 <-> 1053, 1129\n1643 <-> 1638, 1659\n1644 <-> 541, 1522\n1645 <-> 326, 1484\n1646 <-> 458\n1647 <-> 377, 806\n1648 <-> 398\n1649 <-> 1587\n1650 <-> 1071, 1660\n1651 <-> 472\n1652 <-> 700, 1168, 1537, 1601\n1653 <-> 313\n1654 <-> 1037, 1181\n1655 <-> 366\n1656 <-> 303\n1657 <-> 1034\n1658 <-> 348\n1659 <-> 58, 121, 722, 1525, 1643\n1660 <-> 1435, 1438, 1650\n1661 <-> 754, 1172, 1763, 1880\n1662 <-> 444\n1663 <-> 1396\n1664 <-> 1296, 1888\n1665 <-> 14, 1665\n1666 <-> 1265\n1667 <-> 1010, 1272, 1336\n1668 <-> 1668\n1669 <-> 927, 1210, 1522\n1670 <-> 1971\n1671 <-> 192, 1790\n1672 <-> 396, 1099\n1673 <-> 1906, 1950\n1674 <-> 619, 768, 788, 1481\n1675 <-> 1311\n1676 <-> 36\n1677 <-> 1677\n1678 <-> 1226\n1679 <-> 822, 836\n1680 <-> 907\n1681 <-> 551, 1539\n1682 <-> 429, 432, 1924\n1683 <-> 1301, 1848\n1684 <-> 1316\n1685 <-> 1066, 1133\n1686 <-> 185, 1934\n1687 <-> 414, 1750\n1688 <-> 140, 397, 1571\n1689 <-> 195, 1539, 1964\n1690 <-> 910\n1691 <-> 779, 1618, 1876\n1692 <-> 519, 1038\n1693 <-> 1693\n1694 <-> 126, 618, 1694\n1695 <-> 472\n1696 <-> 441\n1697 <-> 1106, 1317, 1579\n1698 <-> 22, 274, 849, 993\n1699 <-> 638\n1700 <-> 1182, 1509\n1701 <-> 402, 962\n1702 <-> 53, 1243\n1703 <-> 358, 1301\n1704 <-> 150, 1889\n1705 <-> 1570, 1826\n1706 <-> 272, 1188, 1526\n1707 <-> 195, 702\n1708 <-> 357, 813\n1709 <-> 19, 1546\n1710 <-> 1161\n1711 <-> 1482\n1712 <-> 1712\n1713 <-> 797\n1714 <-> 115\n1715 <-> 1309\n1716 <-> 1474, 1909\n1717 <-> 1175\n1718 <-> 1047, 1809\n1719 <-> 251\n1720 <-> 62, 561\n1721 <-> 861\n1722 <-> 346\n1723 <-> 1388, 1996\n1724 <-> 304, 1828\n1725 <-> 1988\n1726 <-> 587, 1726\n1727 <-> 674, 1549, 1857\n1728 <-> 1065, 1307, 1821\n1729 <-> 1050\n1730 <-> 104, 1730\n1731 <-> 1731, 1759\n1732 <-> 1319, 1990\n1733 <-> 1109, 1363\n1734 <-> 1031\n1735 <-> 973, 1735\n1736 <-> 526\n1737 <-> 523\n1738 <-> 793, 908\n1739 <-> 279\n1740 <-> 1740\n1741 <-> 1404\n1742 <-> 1742\n1743 <-> 555, 1517\n1744 <-> 434\n1745 <-> 602, 703\n1746 <-> 1392\n1747 <-> 627, 1500, 1513\n1748 <-> 714\n1749 <-> 496, 607, 644, 1943\n1750 <-> 139, 244, 840, 1366, 1687\n1751 <-> 50\n1752 <-> 1086, 1249\n1753 <-> 1211, 1327, 1639\n1754 <-> 1299, 1319\n1755 <-> 651\n1756 <-> 474, 525\n1757 <-> 349, 822\n1758 <-> 560\n1759 <-> 48, 1140, 1175, 1731\n1760 <-> 1150, 1475\n1761 <-> 472, 701, 779\n1762 <-> 892\n1763 <-> 1128, 1365, 1661\n1764 <-> 1878\n1765 <-> 546, 1216\n1766 <-> 142, 642\n1767 <-> 497\n1768 <-> 1772\n1769 <-> 1408, 1438, 1573\n1770 <-> 1154, 1618\n1771 <-> 1256\n1772 <-> 381, 487, 955, 1768\n1773 <-> 1090\n1774 <-> 1425\n1775 <-> 1425, 1902\n1776 <-> 1005\n1777 <-> 87\n1778 <-> 256, 276, 827, 1780\n1779 <-> 1014\n1780 <-> 460, 1039, 1778\n1781 <-> 972\n1782 <-> 954\n1783 <-> 279, 927, 1480, 1549, 1909\n1784 <-> 1542\n1785 <-> 527, 958\n1786 <-> 1786\n1787 <-> 1159, 1517\n1788 <-> 337\n1789 <-> 1538\n1790 <-> 245, 1186, 1671, 1790\n1791 <-> 246, 1925\n1792 <-> 633, 655, 666, 1949\n1793 <-> 1944\n1794 <-> 156\n1795 <-> 737, 1403\n1796 <-> 296, 1067, 1624\n1797 <-> 588\n1798 <-> 642, 1029\n1799 <-> 177, 972\n1800 <-> 715\n1801 <-> 928\n1802 <-> 444, 1346, 1844, 1954\n1803 <-> 317, 1252\n1804 <-> 156\n1805 <-> 481, 659, 1269\n1806 <-> 1390\n1807 <-> 356, 1939\n1808 <-> 1561\n1809 <-> 513, 1718\n1810 <-> 435\n1811 <-> 1450, 1874\n1812 <-> 80, 1550\n1813 <-> 67, 1813\n1814 <-> 1814\n1815 <-> 1359\n1816 <-> 1816\n1817 <-> 280, 640, 762, 1292\n1818 <-> 333, 815, 1431\n1819 <-> 241, 1974\n1820 <-> 253, 1323\n1821 <-> 1256, 1728\n1822 <-> 638, 936\n1823 <-> 374, 1160, 1451\n1824 <-> 423, 657, 719, 969, 1407\n1825 <-> 193\n1826 <-> 1035, 1705\n1827 <-> 70, 959, 1049, 1615\n1828 <-> 374, 1533, 1724\n1829 <-> 208, 801, 1157, 1238\n1830 <-> 551, 1839\n1831 <-> 724, 812\n1832 <-> 1881, 1887\n1833 <-> 688\n1834 <-> 1152\n1835 <-> 680, 1007\n1836 <-> 333\n1837 <-> 482, 744\n1838 <-> 48, 1932\n1839 <-> 32, 1282, 1830\n1840 <-> 82, 1200\n1841 <-> 260\n1842 <-> 134, 141, 881\n1843 <-> 1468\n1844 <-> 1802\n1845 <-> 257, 331, 717, 1281\n1846 <-> 1496\n1847 <-> 193, 258\n1848 <-> 1683\n1849 <-> 178, 324\n1850 <-> 448, 1246\n1851 <-> 455, 1017, 1269, 1331\n1852 <-> 222, 738\n1853 <-> 1244\n1854 <-> 385, 463\n1855 <-> 727\n1856 <-> 958, 1493\n1857 <-> 1727\n1858 <-> 336, 610\n1859 <-> 842, 1334\n1860 <-> 172, 226, 823\n1861 <-> 1861\n1862 <-> 72, 1488\n1863 <-> 1280\n1864 <-> 529\n1865 <-> 1510\n1866 <-> 223, 1989\n1867 <-> 870, 1939\n1868 <-> 556\n1869 <-> 1333\n1870 <-> 1892\n1871 <-> 1549\n1872 <-> 682, 763, 1392\n1873 <-> 1207\n1874 <-> 173, 1811\n1875 <-> 6, 150, 445\n1876 <-> 411, 1691, 1956\n1877 <-> 76, 89, 825, 1403\n1878 <-> 295, 1023, 1764\n1879 <-> 114, 529, 824\n1880 <-> 1092, 1661\n1881 <-> 588, 1005, 1580, 1832\n1882 <-> 944, 1590\n1883 <-> 244\n1884 <-> 232, 487, 1174\n1885 <-> 820, 1153\n1886 <-> 996\n1887 <-> 654, 1832, 1968\n1888 <-> 614, 1664, 1888\n1889 <-> 1704\n1890 <-> 531, 857, 910\n1891 <-> 1448, 1891\n1892 <-> 1494, 1870\n1893 <-> 771\n1894 <-> 1061, 1894\n1895 <-> 216, 809\n1896 <-> 1110\n1897 <-> 1044\n1898 <-> 603\n1899 <-> 1027\n1900 <-> 167, 1274\n1901 <-> 1253, 1427, 1986\n1902 <-> 160, 1164, 1775\n1903 <-> 994, 1507\n1904 <-> 252, 749, 839\n1905 <-> 130, 767, 1356\n1906 <-> 1070, 1673\n1907 <-> 488, 1493\n1908 <-> 145, 1572\n1909 <-> 428, 1716, 1783\n1910 <-> 649, 1611\n1911 <-> 1356\n1912 <-> 96\n1913 <-> 1913\n1914 <-> 1360, 1389, 1531\n1915 <-> 1139, 1357, 1443\n1916 <-> 348, 494\n1917 <-> 499, 1348\n1918 <-> 1091\n1919 <-> 487, 1290\n1920 <-> 690\n1921 <-> 1558\n1922 <-> 237\n1923 <-> 1086\n1924 <-> 393, 834, 1682\n1925 <-> 833, 1791\n1926 <-> 1321\n1927 <-> 1230, 1927\n1928 <-> 1421, 1928\n1929 <-> 1572, 1929\n1930 <-> 1044\n1931 <-> 112, 1177, 1995\n1932 <-> 711, 1838\n1933 <-> 669, 1085\n1934 <-> 804, 1686\n1935 <-> 652\n1936 <-> 1467\n1937 <-> 520, 1141\n1938 <-> 679\n1939 <-> 478, 1102, 1807, 1867\n1940 <-> 595\n1941 <-> 462\n1942 <-> 497, 904\n1943 <-> 1749\n1944 <-> 361, 1604, 1793\n1945 <-> 1945\n1946 <-> 695, 1337\n1947 <-> 204\n1948 <-> 1161\n1949 <-> 1792\n1950 <-> 437, 515, 690, 1673\n1951 <-> 853, 999\n1952 <-> 1436\n1953 <-> 367, 373, 1953\n1954 <-> 176, 1802\n1955 <-> 438\n1956 <-> 135, 1876\n1957 <-> 1957\n1958 <-> 1388\n1959 <-> 545, 1369\n1960 <-> 123, 1586\n1961 <-> 411\n1962 <-> 387\n1963 <-> 534, 1349\n1964 <-> 1689\n1965 <-> 725, 1268, 1965\n1966 <-> 759\n1967 <-> 111\n1968 <-> 1887\n1969 <-> 433, 847\n1970 <-> 955\n1971 <-> 309, 411, 1670\n1972 <-> 431\n1973 <-> 464\n1974 <-> 1819\n1975 <-> 7, 1184\n1976 <-> 734, 866, 1513\n1977 <-> 1083, 1376\n1978 <-> 46, 387, 599, 1462\n1979 <-> 82\n1980 <-> 1238\n1981 <-> 323\n1982 <-> 1090\n1983 <-> 197, 791\n1984 <-> 1237, 1984\n1985 <-> 564, 868, 1351\n1986 <-> 934, 1377, 1594, 1901\n1987 <-> 400, 890, 1987\n1988 <-> 1521, 1725\n1989 <-> 389, 1866\n1990 <-> 315, 1428, 1732\n1991 <-> 1289\n1992 <-> 125, 158, 277, 785\n1993 <-> 290, 1327, 1521\n1994 <-> 275, 1101\n1995 <-> 1422, 1931\n1996 <-> 24, 544, 590, 1418, 1723\n1997 <-> 750, 1997\n1998 <-> 643, 831, 1100\n1999 <-> 1162"