Inverted Index Generator.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Taking Input Path To Directory In Which All Files Are Present\n",
    "\n",
    "Path Should be in either of these format\n",
    "e.g. C:/users/username/path_to_directory       or      C:\\\\users\\\\username\\\\path_to_directory"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import os\n",
    "\n",
    "#path = input()\n",
    "path = r\".\\alldocs\"\n",
    "\n",
    "files = []\n",
    "# r=root, d=directories, f = files\n",
    "for r, d, f in os.walk(path):\n",
    "    for file in f:\n",
    "            files.append(os.path.join(r, file))\n",
    "#print(files)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Storing Stop_Words From stoplist.txt file to Dictionary"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "#path_stop = input()\n",
    "path_stop = r\".\\stopwords.txt\" \n",
    "\n",
    "stop_words = dict()\n",
    "index = 1;\n",
    "with open(path_stop,'r', encoding='utf8', errors='ignore') as f:\n",
    "    for line in f.readlines():\n",
    "        stop_words[line.rstrip()]=index\n",
    "        index=index+1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Creating Different Dictionaries"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "termids=dict()\n",
    "docids=dict()\n",
    "term_index=dict()\n",
    "term_index_list=[]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Converting Words To Lower Case"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "def convert_lower_case(text):\n",
    "     return text.lower()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Library For Tokenizing Words"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "import nltk\n",
    "def split_words(text):\n",
    "     return nltk.word_tokenize(text)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Checking Whether A Tokenize Word Have Appeared Before"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "def check_termid(text):\n",
    "    if text in termids:\n",
    "        return True\n",
    "    else:\n",
    "        return False"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Stemming Tokenize Words Using Porter Stemmer"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "from nltk.stem.porter import *\n",
    "def apply_stemming(tokens):\n",
    "    stemmer = PorterStemmer()\n",
    "    return stemmer.stem(tokens)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Adding Values in DocIDs Dictionary"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "def add_to_docids(pathName,docid):\n",
    "    docName = os.path.basename(pathName)\n",
    "    docids[docName] = docid"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Adding Values in TermIDs Dictionary"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "def add_to_termids(word,termid):\n",
    "    termids[word]=termid"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Checking Previous Occurences of the Tokenize Words"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "def get_termid(word):\n",
    "    return termids.get(word)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Adding Words to TermIndex"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [],
   "source": [
    "def add_to_term_index_list(termid,docid,termPosition):\n",
    "    term_index_values = [termid,1,1,docid,termPosition]\n",
    "    term_index_list.append(term_index_values)\n",
    "def add_to_term_index(termid,docid,termPosition):\n",
    "    term_index_values = [1,1,docid,termPosition]\n",
    "    term_index[termid]=term_index_values\n",
    "def update_term_index(termid,docid,termPosition):\n",
    "    term_index_values = term_index.get(termid)\n",
    "    length=len(term_index_values)\n",
    "    if docid-term_index_values[length-2]!=0:\n",
    "        term_index_values[1]=term_index_values[1]+1\n",
    "    term_index_values[0]=term_index_values[0]+1\n",
    "    values_update=[docid,termPosition]\n",
    "    result = term_index_values+values_update\n",
    "    new_dict = dict()\n",
    "    new_dict[termid]=result\n",
    "    term_index.update(new_dict)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# A For Loop For Parsing Each File To Extract Relevant Information\n",
    "\n",
    "To Create Docids dictionary,Termids dictionay and TermIndex"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 439\n",
      "2 2707\n",
      "3 792\n",
      "4 1097\n",
      "5 1055\n",
      "6 269\n",
      "7 929\n",
      "8 5881\n",
      "9 2540\n",
      "10 2962\n",
      "11 7224\n",
      "12 20865\n",
      "13 249\n",
      "14 21478\n",
      "15 1264\n",
      "16 2304\n",
      "17 526\n",
      "18 8231\n",
      "19 895\n",
      "20 514\n",
      "21 2807\n",
      "22 958\n",
      "23 796\n",
      "24 1577\n",
      "25 782\n",
      "26 6980\n",
      "27 15582\n",
      "28 5934\n",
      "29 9702\n",
      "30 1022\n",
      "31 2374\n",
      "32 2228\n",
      "33 361\n",
      "34 1124\n",
      "35 11679\n",
      "36 742\n",
      "37 2509\n",
      "38 666\n",
      "39 2220\n",
      "40 2968\n",
      "41 503\n",
      "42 1228\n",
      "43 539\n",
      "44 322\n",
      "45 1164\n",
      "46 501\n",
      "47 2781\n",
      "48 1605\n",
      "49 24756\n",
      "50 828\n",
      "51 1353\n",
      "52 411\n",
      "53 2867\n",
      "54 296\n",
      "55 8574\n",
      "56 1825\n",
      "57 1231\n",
      "58 134\n",
      "59 3033\n",
      "60 1599\n",
      "61 2891\n",
      "62 633\n",
      "63 5331\n",
      "64 794\n",
      "65 1946\n",
      "66 1835\n",
      "67 4060\n",
      "68 970\n",
      "69 2436\n",
      "70 921\n",
      "71 4641\n",
      "72 80\n",
      "73 312\n",
      "74 831\n",
      "75 2351\n",
      "76 11408\n",
      "77 807\n",
      "78 3055\n",
      "79 709\n",
      "80 458\n",
      "81 2546\n",
      "82 1412\n",
      "83 1675\n",
      "84 2885\n",
      "85 473\n",
      "86 4492\n",
      "87 986\n",
      "88 1282\n",
      "89 8114\n",
      "90 411\n",
      "91 5946\n",
      "92 498\n",
      "93 2663\n",
      "94 4178\n",
      "95 5970\n",
      "96 2073\n",
      "97 444\n",
      "98 3785\n",
      "99 1725\n",
      "100 9238\n",
      "101 1652\n",
      "102 2061\n",
      "103 369\n",
      "104 211\n",
      "105 435\n",
      "106 737\n",
      "107 5981\n",
      "108 1072\n",
      "109 435\n",
      "110 352\n",
      "111 614\n",
      "112 1012\n",
      "113 2903\n",
      "114 905\n",
      "115 254\n",
      "116 566\n",
      "117 1003\n",
      "118 2639\n",
      "119 5\n",
      "120 1193\n",
      "121 358\n",
      "122 4201\n",
      "123 1548\n",
      "124 3631\n",
      "125 1817\n",
      "126 13886\n",
      "127 990\n",
      "128 2406\n",
      "129 385\n",
      "130 1546\n",
      "131 112\n",
      "132 1351\n",
      "133 1238\n",
      "134 1387\n",
      "135 5505\n",
      "136 3620\n",
      "137 610\n",
      "138 5577\n",
      "139 3696\n",
      "140 1590\n",
      "141 5029\n",
      "142 5337\n",
      "143 559\n",
      "144 534\n",
      "145 1989\n",
      "146 137\n",
      "147 4893\n",
      "148 679\n",
      "149 2871\n",
      "150 1944\n",
      "151 372\n",
      "152 25021\n",
      "153 3460\n",
      "154 707\n",
      "155 3836\n",
      "156 950\n",
      "157 1187\n",
      "158 125\n",
      "159 646\n",
      "160 1059\n",
      "161 249\n",
      "162 7458\n",
      "163 434\n",
      "164 373\n",
      "165 1593\n",
      "166 1292\n",
      "167 830\n",
      "168 2946\n",
      "169 2555\n",
      "170 354\n",
      "171 4955\n",
      "172 2388\n",
      "173 1995\n",
      "174 4669\n",
      "175 890\n",
      "176 890\n",
      "177 5401\n",
      "178 1364\n",
      "179 585\n",
      "180 205\n",
      "181 2846\n",
      "182 205\n",
      "183 2148\n",
      "184 767\n",
      "185 254\n",
      "186 1512\n",
      "187 1151\n",
      "188 1786\n",
      "189 370\n",
      "190 1201\n",
      "191 1001\n",
      "192 10412\n",
      "193 3661\n",
      "194 370\n",
      "195 2171\n",
      "196 2234\n",
      "197 5517\n",
      "198 509\n",
      "199 11945\n",
      "200 5313\n",
      "201 412\n",
      "202 2536\n",
      "203 1514\n",
      "204 2067\n",
      "205 641\n",
      "206 596\n",
      "207 187\n",
      "208 1240\n",
      "209 5159\n",
      "210 1868\n",
      "211 301\n",
      "212 83\n",
      "213 423\n",
      "214 862\n",
      "215 409\n",
      "216 108\n",
      "217 789\n",
      "218 5929\n",
      "219 3824\n",
      "220 4792\n",
      "221 596\n",
      "222 1184\n",
      "223 1368\n",
      "224 753\n",
      "225 2525\n",
      "226 601\n",
      "227 994\n",
      "228 3498\n",
      "229 4953\n",
      "230 417\n",
      "231 6514\n",
      "232 792\n",
      "233 13505\n",
      "234 305\n",
      "235 1153\n",
      "236 372\n",
      "237 4614\n",
      "238 21427\n",
      "239 2152\n",
      "240 474\n",
      "241 809\n",
      "242 424\n",
      "243 750\n",
      "244 2989\n",
      "245 2437\n",
      "246 969\n",
      "247 2952\n",
      "248 456\n",
      "249 1928\n",
      "250 513\n",
      "251 149\n",
      "252 325\n",
      "253 1288\n",
      "254 545\n",
      "255 1616\n",
      "256 400\n",
      "257 352\n",
      "258 900\n",
      "259 377\n",
      "260 2338\n",
      "261 1229\n",
      "262 774\n",
      "263 3228\n",
      "264 230\n",
      "265 1373\n",
      "266 4410\n",
      "267 11144\n",
      "268 4903\n",
      "269 927\n",
      "270 2740\n",
      "271 724\n",
      "272 26024\n",
      "273 712\n",
      "274 2654\n",
      "275 17832\n",
      "276 520\n",
      "277 990\n",
      "278 2674\n",
      "279 155\n",
      "280 331\n",
      "281 4704\n",
      "282 14234\n",
      "283 1755\n",
      "284 11612\n",
      "285 1673\n",
      "286 2672\n",
      "287 3737\n",
      "288 719\n",
      "289 3290\n",
      "290 724\n",
      "291 15748\n",
      "292 774\n",
      "293 2016\n",
      "294 1680\n",
      "295 670\n",
      "296 1202\n",
      "297 1315\n",
      "298 460\n",
      "299 374\n",
      "300 2829\n",
      "301 1116\n",
      "302 2808\n",
      "303 2266\n",
      "304 1341\n",
      "305 3600\n",
      "306 3158\n",
      "307 399\n",
      "308 490\n",
      "309 3571\n",
      "310 1401\n",
      "311 2387\n",
      "312 581\n",
      "313 600\n",
      "314 4086\n",
      "315 1322\n",
      "316 571\n",
      "317 1838\n",
      "318 2093\n",
      "319 7007\n",
      "320 1391\n",
      "321 1141\n",
      "322 494\n",
      "323 441\n",
      "324 21718\n",
      "325 19061\n",
      "326 1210\n",
      "327 2466\n",
      "328 1763\n",
      "329 819\n",
      "330 2421\n",
      "331 10446\n",
      "332 121\n",
      "333 2133\n",
      "334 19390\n",
      "335 1230\n",
      "336 4491\n",
      "337 228\n",
      "338 14516\n",
      "339 1461\n",
      "340 4185\n",
      "341 735\n",
      "342 1173\n",
      "343 994\n",
      "344 510\n",
      "345 1318\n",
      "346 613\n",
      "347 1096\n",
      "348 2814\n",
      "349 1831\n",
      "350 4648\n",
      "351 686\n",
      "352 1408\n",
      "353 369\n",
      "354 1203\n",
      "355 632\n",
      "356 467\n",
      "357 5356\n",
      "358 4590\n",
      "359 1590\n",
      "360 3870\n",
      "361 1157\n",
      "362 1868\n",
      "363 823\n",
      "364 6948\n",
      "365 313\n",
      "366 10843\n",
      "367 239\n",
      "368 168\n",
      "369 1402\n",
      "370 5856\n",
      "371 53\n",
      "372 1693\n",
      "373 1221\n",
      "374 728\n",
      "375 1562\n",
      "376 2832\n",
      "377 1788\n",
      "378 3934\n",
      "379 1041\n",
      "380 332\n",
      "381 208\n",
      "382 3622\n",
      "383 2103\n",
      "384 360\n",
      "385 4389\n",
      "386 3775\n",
      "387 4273\n",
      "388 941\n",
      "389 4062\n",
      "390 2693\n",
      "391 2291\n",
      "392 1433\n",
      "393 898\n",
      "394 1394\n",
      "395 13908\n",
      "396 1568\n",
      "397 378\n",
      "398 16129\n",
      "399 6698\n",
      "400 1134\n",
      "401 687\n",
      "402 156\n",
      "403 1308\n",
      "404 1778\n",
      "405 1775\n",
      "406 3332\n",
      "407 443\n",
      "408 21435\n",
      "409 264\n",
      "410 754\n",
      "411 11045\n",
      "412 2020\n",
      "413 350\n",
      "414 28\n",
      "415 3680\n",
      "416 3045\n",
      "417 9343\n",
      "418 1418\n",
      "419 731\n",
      "420 211\n",
      "421 5299\n",
      "422 2793\n",
      "423 1407\n",
      "424 6114\n",
      "425 1431\n",
      "426 23688\n",
      "427 957\n",
      "428 2587\n",
      "429 9410\n",
      "430 1586\n",
      "431 380\n",
      "432 848\n",
      "433 3334\n",
      "434 89\n",
      "435 43\n",
      "436 1272\n",
      "437 5126\n",
      "438 5051\n",
      "439 649\n",
      "440 6034\n",
      "441 211\n",
      "442 287\n",
      "443 125\n",
      "444 1408\n",
      "445 3106\n",
      "446 187\n",
      "447 547\n",
      "448 2511\n",
      "449 6466\n",
      "450 2035\n",
      "451 297\n",
      "452 1314\n",
      "453 150\n",
      "454 917\n",
      "455 5684\n",
      "456 136\n",
      "457 295\n",
      "458 1219\n",
      "459 4197\n",
      "460 1395\n",
      "461 964\n",
      "462 2874\n",
      "463 160\n",
      "464 2247\n",
      "465 373\n",
      "466 692\n",
      "467 397\n",
      "468 345\n",
      "469 486\n",
      "470 2859\n",
      "471 3498\n",
      "472 2671\n",
      "473 1625\n",
      "474 2126\n",
      "475 5779\n",
      "476 1084\n",
      "477 4041\n",
      "478 3251\n",
      "479 138\n",
      "480 539\n",
      "481 379\n",
      "482 1752\n",
      "483 1589\n",
      "484 4125\n",
      "485 609\n",
      "486 866\n",
      "487 1431\n",
      "488 2474\n",
      "489 594\n",
      "490 957\n",
      "491 325\n",
      "492 225\n",
      "493 1871\n",
      "494 4611\n",
      "495 2501\n",
      "496 16577\n",
      "497 1306\n",
      "498 2193\n",
      "499 661\n",
      "500 2252\n",
      "501 696\n",
      "502 1751\n",
      "503 104\n",
      "504 2965\n",
      "505 2089\n",
      "506 1792\n",
      "507 1820\n",
      "508 3507\n",
      "509 7004\n",
      "510 1049\n",
      "511 463\n",
      "512 423\n",
      "513 1921\n",
      "514 1641\n",
      "515 3352\n",
      "516 1161\n",
      "517 9965\n",
      "518 1308\n",
      "519 20725\n",
      "520 1007\n",
      "521 237\n",
      "522 2656\n",
      "523 334\n",
      "524 1035\n",
      "525 369\n",
      "526 1239\n",
      "527 2833\n",
      "528 3487\n",
      "529 476\n",
      "530 10442\n",
      "531 198\n",
      "532 3717\n",
      "533 2286\n",
      "534 1017\n",
      "535 626\n",
      "536 1758\n",
      "537 279\n",
      "538 1011\n",
      "539 1145\n",
      "540 238\n",
      "541 689\n",
      "542 723\n",
      "543 22461\n",
      "544 1090\n",
      "545 1468\n",
      "546 2105\n",
      "547 488\n",
      "548 19617\n",
      "549 2213\n",
      "550 831\n",
      "551 108\n",
      "552 450\n",
      "553 107\n",
      "554 2465\n",
      "555 1065\n",
      "556 3252\n",
      "557 1793\n",
      "558 1674\n",
      "559 2439\n",
      "560 2199\n",
      "561 1607\n",
      "562 7863\n",
      "563 127\n",
      "564 746\n",
      "565 271\n",
      "566 2483\n",
      "567 2768\n",
      "568 1703\n",
      "569 1678\n",
      "570 238\n",
      "571 1352\n",
      "572 1392\n",
      "573 1726\n",
      "574 215\n",
      "575 437\n",
      "576 8491\n",
      "577 16385\n",
      "578 1687\n",
      "579 378\n",
      "580 3634\n",
      "581 2136\n",
      "582 518\n",
      "583 1265\n",
      "584 1313\n",
      "585 886\n",
      "586 19457\n",
      "587 2195\n",
      "588 1214\n",
      "589 4348\n",
      "590 2449\n",
      "591 374\n",
      "592 2107\n",
      "593 6273\n",
      "594 2599\n",
      "595 601\n",
      "596 1803\n",
      "597 149\n",
      "598 827\n",
      "599 466\n",
      "600 569\n",
      "601 956\n",
      "602 389\n",
      "603 2685\n",
      "604 1012\n",
      "605 411\n",
      "606 573\n",
      "607 797\n",
      "608 750\n",
      "609 948\n",
      "610 1148\n",
      "611 5284\n",
      "612 3516\n",
      "613 386\n",
      "614 5174\n",
      "615 5201\n",
      "616 153\n",
      "617 15467\n",
      "618 1605\n",
      "619 555\n",
      "620 900\n",
      "621 1937\n",
      "622 5531\n",
      "623 978\n",
      "624 1085\n",
      "625 1105\n",
      "626 463\n",
      "627 413\n",
      "628 10953\n",
      "629 2608\n",
      "630 1046\n",
      "631 4363\n",
      "632 1163\n",
      "633 502\n",
      "634 2652\n",
      "635 3726\n",
      "636 2430\n",
      "637 895\n",
      "638 5141\n",
      "639 979\n",
      "640 3678\n",
      "641 3623\n",
      "642 4023\n",
      "643 1419\n",
      "644 3718\n",
      "645 414\n",
      "646 262\n",
      "647 1299\n",
      "648 3122\n",
      "649 1262\n",
      "650 3852\n",
      "651 541\n",
      "652 4856\n",
      "653 3460\n",
      "654 385\n",
      "655 15016\n",
      "656 7044\n",
      "657 1740\n",
      "658 302\n",
      "659 3836\n",
      "660 1817\n",
      "661 2463\n",
      "662 1520\n",
      "663 1243\n",
      "664 2361\n",
      "665 492\n",
      "666 2203\n",
      "667 3920\n",
      "668 662\n",
      "669 7612\n",
      "670 2813\n",
      "671 826\n",
      "672 1197\n",
      "673 2538\n",
      "674 422\n",
      "675 3868\n",
      "676 944\n",
      "677 767\n",
      "678 3635\n",
      "679 1420\n",
      "680 1945\n",
      "681 1771\n",
      "682 668\n",
      "683 1150\n",
      "684 368\n",
      "685 2221\n",
      "686 1961\n",
      "687 2898\n",
      "688 5359\n",
      "689 598\n",
      "690 2466\n",
      "691 7604\n",
      "692 1670\n",
      "693 201\n",
      "694 1429\n",
      "695 1852\n",
      "696 1005\n",
      "697 2242\n",
      "698 1308\n",
      "699 2073\n",
      "700 3065\n",
      "701 2729\n",
      "702 1618\n",
      "703 3131\n",
      "704 2243\n",
      "705 1377\n",
      "706 736\n",
      "707 918\n",
      "708 456\n",
      "709 1292\n",
      "710 977\n",
      "711 5599\n",
      "712 2113\n",
      "713 1394\n",
      "714 2267\n",
      "715 964\n",
      "716 581\n",
      "717 3542\n",
      "718 314\n",
      "719 13914\n",
      "720 666\n",
      "721 315\n",
      "722 948\n",
      "723 4843\n",
      "724 379\n",
      "725 1334\n",
      "726 1303\n",
      "727 1206\n",
      "728 2387\n",
      "729 2441\n",
      "730 3384\n",
      "731 1701\n",
      "732 7086\n",
      "733 841\n",
      "734 1494\n",
      "735 2791\n",
      "736 155\n",
      "737 319\n",
      "738 1204\n",
      "739 1297\n",
      "740 2058\n",
      "741 803\n",
      "742 7206\n",
      "743 224\n",
      "744 2100\n",
      "745 890\n",
      "746 780\n",
      "747 908\n",
      "748 229\n",
      "749 11179\n",
      "750 419\n",
      "751 1629\n",
      "752 1685\n",
      "753 311\n",
      "754 1406\n",
      "755 708\n",
      "756 1473\n",
      "757 332\n",
      "758 707\n",
      "759 805\n",
      "760 6101\n",
      "761 1185\n",
      "762 1736\n",
      "763 2833\n",
      "764 1297\n",
      "765 3798\n",
      "766 3111\n",
      "767 1361\n",
      "768 1667\n",
      "769 2165\n",
      "770 2745\n",
      "771 764\n",
      "772 422\n",
      "773 5718\n",
      "774 1505\n",
      "775 4582\n",
      "776 2341\n",
      "777 2757\n",
      "778 1291\n",
      "779 6812\n",
      "780 951\n",
      "781 169\n",
      "782 9511\n",
      "783 3218\n",
      "784 403\n",
      "785 2714\n",
      "786 1459\n",
      "787 893\n",
      "788 1471\n",
      "789 3672\n",
      "790 446\n",
      "791 503\n",
      "792 576\n",
      "793 19506\n",
      "794 641\n",
      "795 379\n",
      "796 872\n",
      "797 294\n",
      "798 1074\n",
      "799 19286\n",
      "800 73\n",
      "801 1260\n",
      "802 3348\n",
      "803 440\n",
      "804 676\n",
      "805 1607\n",
      "806 601\n",
      "807 2988\n",
      "808 3952\n",
      "809 4225\n",
      "810 3037\n",
      "811 402\n",
      "812 648\n",
      "813 379\n",
      "814 2240\n",
      "815 657\n",
      "816 609\n",
      "817 511\n",
      "818 3481\n",
      "819 6463\n",
      "820 5051\n",
      "821 721\n",
      "822 25288\n",
      "823 2192\n",
      "824 674\n",
      "825 356\n",
      "826 6372\n",
      "827 696\n",
      "828 323\n",
      "829 1038\n",
      "830 383\n",
      "831 662\n",
      "832 490\n",
      "833 850\n",
      "834 7042\n",
      "835 736\n",
      "836 3087\n",
      "837 698\n",
      "838 801\n",
      "839 9821\n",
      "840 277\n",
      "841 3473\n",
      "842 1330\n",
      "843 630\n",
      "844 650\n",
      "845 2259\n",
      "846 646\n",
      "847 414\n",
      "848 1720\n",
      "849 23905\n",
      "850 92\n",
      "851 3354\n",
      "852 902\n",
      "853 2733\n",
      "854 1197\n",
      "855 1463\n",
      "856 17658\n",
      "857 4254\n",
      "858 9238\n",
      "859 493\n",
      "860 950\n",
      "861 549\n",
      "862 1186\n",
      "863 1055\n",
      "864 4186\n",
      "865 1355\n",
      "866 1107\n",
      "867 578\n",
      "868 4402\n",
      "869 174\n",
      "870 1362\n",
      "871 1774\n",
      "872 752\n",
      "873 7558\n",
      "874 324\n",
      "875 651\n",
      "876 2174\n",
      "877 693\n",
      "878 749\n",
      "879 844\n",
      "880 521\n",
      "881 5591\n",
      "882 687\n",
      "883 868\n",
      "884 421\n",
      "885 415\n",
      "886 322\n",
      "887 1445\n",
      "888 577\n",
      "889 503\n",
      "890 1085\n",
      "891 486\n",
      "892 274\n",
      "893 1459\n",
      "894 816\n",
      "895 133\n",
      "896 4000\n",
      "897 345\n",
      "898 1727\n",
      "899 242\n",
      "900 823\n",
      "901 2699\n",
      "902 2880\n",
      "903 8221\n",
      "904 1363\n",
      "905 1934\n",
      "906 963\n",
      "907 49\n",
      "908 54\n",
      "909 1217\n",
      "910 2028\n",
      "911 2233\n",
      "912 194\n",
      "913 1980\n",
      "914 2461\n",
      "915 906\n",
      "916 1325\n",
      "917 2225\n",
      "918 3695\n",
      "919 523\n",
      "920 29\n",
      "921 334\n",
      "922 385\n",
      "923 1242\n",
      "924 611\n",
      "925 483\n",
      "926 515\n",
      "927 1518\n",
      "928 906\n",
      "929 6657\n",
      "930 241\n",
      "931 1269\n",
      "932 6225\n",
      "933 1609\n",
      "934 2661\n",
      "935 1113\n",
      "936 265\n",
      "937 1929\n",
      "938 701\n",
      "939 2802\n",
      "940 217\n",
      "941 53\n",
      "942 4589\n",
      "943 2848\n",
      "944 2308\n",
      "945 2356\n",
      "946 5635\n",
      "947 481\n",
      "948 3087\n",
      "949 463\n",
      "950 2411\n",
      "951 1418\n",
      "952 4623\n",
      "953 4574\n",
      "954 1229\n",
      "955 2474\n",
      "956 208\n",
      "957 155\n",
      "958 1018\n",
      "959 329\n",
      "960 2216\n",
      "961 744\n",
      "962 1110\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "963 421\n",
      "964 178\n",
      "965 415\n",
      "966 593\n",
      "967 776\n",
      "968 849\n",
      "969 424\n",
      "970 660\n",
      "971 2036\n",
      "972 1187\n",
      "973 2248\n",
      "974 353\n",
      "975 3707\n",
      "976 1546\n",
      "977 9399\n",
      "978 2800\n",
      "979 1823\n",
      "980 1455\n",
      "981 156\n",
      "982 1239\n",
      "983 3585\n",
      "984 1551\n",
      "985 169\n",
      "986 212\n",
      "987 762\n",
      "988 1079\n",
      "989 4568\n",
      "990 2449\n",
      "991 348\n",
      "992 511\n",
      "993 775\n",
      "994 2521\n",
      "995 1234\n",
      "996 514\n",
      "997 996\n",
      "998 1153\n",
      "999 3623\n",
      "1000 7289\n",
      "1001 287\n",
      "1002 695\n",
      "1003 2399\n",
      "1004 4155\n",
      "1005 2048\n",
      "1006 980\n",
      "1007 1279\n",
      "1008 1037\n",
      "1009 138\n",
      "1010 2147\n",
      "1011 3390\n",
      "1012 19671\n",
      "1013 831\n",
      "1014 831\n",
      "1015 1838\n",
      "1016 1003\n",
      "1017 307\n",
      "1018 457\n",
      "1019 6673\n",
      "1020 7181\n",
      "1021 286\n",
      "1022 526\n",
      "1023 478\n",
      "1024 4152\n",
      "1025 2788\n",
      "1026 153\n",
      "1027 700\n",
      "1028 6760\n",
      "1029 668\n",
      "1030 720\n",
      "1031 11789\n",
      "1032 791\n",
      "1033 4991\n",
      "1034 3844\n",
      "1035 171\n",
      "1036 1559\n",
      "1037 616\n",
      "1038 4803\n",
      "1039 553\n",
      "1040 1971\n",
      "1041 2068\n",
      "1042 271\n",
      "1043 394\n",
      "1044 859\n",
      "1045 3488\n",
      "1046 17117\n",
      "1047 2381\n",
      "1048 6145\n",
      "1049 5801\n",
      "1050 3572\n",
      "1051 2501\n",
      "1052 2120\n",
      "1053 460\n",
      "1054 5253\n",
      "1055 5571\n",
      "1056 637\n",
      "1057 311\n",
      "1058 766\n",
      "1059 433\n",
      "1060 15993\n",
      "1061 2553\n",
      "1062 263\n",
      "1063 1405\n",
      "1064 996\n",
      "1065 1634\n",
      "1066 2656\n",
      "1067 5761\n",
      "1068 421\n",
      "1069 356\n",
      "1070 1292\n",
      "1071 248\n",
      "1072 3428\n",
      "1073 1141\n",
      "1074 35\n",
      "1075 496\n",
      "1076 209\n",
      "1077 8601\n",
      "1078 2154\n",
      "1079 3971\n",
      "1080 1505\n",
      "1081 338\n",
      "1082 364\n",
      "1083 730\n",
      "1084 104\n",
      "1085 323\n",
      "1086 399\n",
      "1087 735\n",
      "1088 6386\n",
      "1089 1228\n",
      "1090 1480\n",
      "1091 760\n",
      "1092 1677\n",
      "1093 556\n",
      "1094 465\n",
      "1095 369\n",
      "1096 1634\n",
      "1097 610\n",
      "1098 875\n",
      "1099 2490\n",
      "1100 1623\n",
      "1101 5773\n",
      "1102 935\n",
      "1103 2338\n",
      "1104 1218\n",
      "1105 3162\n",
      "1106 1352\n",
      "1107 2430\n",
      "1108 1803\n",
      "1109 826\n",
      "1110 2286\n",
      "1111 2821\n",
      "1112 1079\n",
      "1113 526\n",
      "1114 1100\n",
      "1115 2190\n",
      "1116 531\n",
      "1117 1018\n",
      "1118 3381\n",
      "1119 1002\n",
      "1120 2770\n",
      "1121 251\n",
      "1122 867\n",
      "1123 163\n",
      "1124 1183\n",
      "1125 224\n",
      "1126 344\n",
      "1127 183\n",
      "1128 1500\n",
      "1129 40\n",
      "1130 1392\n",
      "1131 109\n",
      "1132 7588\n",
      "1133 1163\n",
      "1134 4356\n",
      "1135 584\n",
      "1136 655\n",
      "1137 1194\n",
      "1138 1680\n",
      "1139 365\n",
      "1140 2888\n",
      "1141 2890\n",
      "1142 1372\n",
      "1143 669\n",
      "1144 1074\n",
      "1145 4543\n",
      "1146 2017\n",
      "1147 132\n",
      "1148 750\n",
      "1149 984\n",
      "1150 9413\n",
      "1151 399\n",
      "1152 1696\n",
      "1153 18\n",
      "1154 388\n",
      "1155 355\n",
      "1156 2315\n",
      "1157 121\n",
      "1158 158\n",
      "1159 111\n",
      "1160 534\n",
      "1161 6548\n",
      "1162 1418\n",
      "1163 1154\n",
      "1164 675\n",
      "1165 148\n",
      "1166 4580\n",
      "1167 1667\n",
      "1168 2883\n",
      "1169 618\n",
      "1170 1090\n",
      "1171 764\n",
      "1172 1422\n",
      "1173 388\n",
      "1174 682\n",
      "1175 356\n",
      "1176 343\n",
      "1177 3952\n",
      "1178 312\n",
      "1179 478\n",
      "1180 12980\n",
      "1181 3051\n",
      "1182 1244\n",
      "1183 1867\n",
      "1184 256\n",
      "1185 436\n",
      "1186 1714\n",
      "1187 1528\n",
      "1188 858\n",
      "1189 2126\n",
      "1190 973\n",
      "1191 1457\n",
      "1192 5181\n",
      "1193 1128\n",
      "1194 1875\n",
      "1195 297\n",
      "1196 709\n",
      "1197 1202\n",
      "1198 2986\n",
      "1199 670\n",
      "1200 3768\n",
      "1201 1208\n",
      "1202 3057\n",
      "1203 198\n",
      "1204 2404\n",
      "1205 283\n",
      "1206 322\n",
      "1207 511\n",
      "1208 160\n",
      "1209 1794\n",
      "1210 3514\n",
      "1211 253\n",
      "1212 595\n",
      "1213 2044\n",
      "1214 403\n",
      "1215 21742\n",
      "1216 241\n",
      "1217 4096\n",
      "1218 819\n",
      "1219 7453\n",
      "1220 523\n",
      "1221 1433\n",
      "1222 2488\n",
      "1223 1283\n",
      "1224 2349\n",
      "1225 466\n",
      "1226 1034\n",
      "1227 8717\n",
      "1228 359\n",
      "1229 796\n",
      "1230 302\n",
      "1231 926\n",
      "1232 1199\n",
      "1233 838\n",
      "1234 10805\n",
      "1235 437\n",
      "1236 1778\n",
      "1237 1149\n",
      "1238 2356\n",
      "1239 719\n",
      "1240 608\n",
      "1241 14968\n",
      "1242 2432\n",
      "1243 832\n",
      "1244 12208\n",
      "1245 5391\n",
      "1246 1184\n",
      "1247 2752\n",
      "1248 1481\n",
      "1249 2765\n",
      "1250 703\n",
      "1251 649\n",
      "1252 758\n",
      "1253 390\n",
      "1254 2151\n",
      "1255 615\n",
      "1256 2856\n",
      "1257 7786\n",
      "1258 118\n",
      "1259 1250\n",
      "1260 1267\n",
      "1261 884\n",
      "1262 652\n",
      "1263 1380\n",
      "1264 439\n",
      "1265 1468\n",
      "1266 1121\n",
      "1267 1649\n",
      "1268 785\n",
      "1269 2202\n",
      "1270 408\n",
      "1271 781\n",
      "1272 1162\n",
      "1273 3877\n",
      "1274 785\n",
      "1275 264\n",
      "1276 714\n",
      "1277 3165\n",
      "1278 1207\n",
      "1279 605\n",
      "1280 3721\n",
      "1281 1280\n",
      "1282 772\n",
      "1283 1177\n",
      "1284 805\n",
      "1285 4702\n",
      "1286 333\n",
      "1287 287\n",
      "1288 2417\n",
      "1289 8659\n",
      "1290 491\n",
      "1291 9514\n",
      "1292 516\n",
      "1293 3226\n",
      "1294 276\n",
      "1295 12299\n",
      "1296 7490\n",
      "1297 2079\n",
      "1298 10907\n",
      "1299 1148\n",
      "1300 5443\n",
      "1301 1135\n",
      "1302 374\n",
      "1303 1714\n",
      "1304 355\n",
      "1305 1366\n",
      "1306 1447\n",
      "1307 208\n",
      "1308 5\n",
      "1309 4825\n",
      "1310 72\n",
      "1311 907\n",
      "1312 992\n",
      "1313 498\n",
      "1314 501\n",
      "1315 1263\n",
      "1316 8393\n",
      "1317 826\n",
      "1318 376\n",
      "1319 1249\n",
      "1320 1201\n",
      "1321 4998\n",
      "1322 1173\n",
      "1323 1116\n",
      "1324 1142\n",
      "1325 415\n",
      "1326 412\n",
      "1327 585\n",
      "1328 567\n",
      "1329 543\n",
      "1330 668\n",
      "1331 384\n",
      "1332 325\n",
      "1333 470\n",
      "1334 533\n",
      "1335 460\n",
      "1336 804\n",
      "1337 82\n",
      "1338 1466\n",
      "1339 588\n",
      "1340 43\n",
      "1341 1565\n",
      "1342 7\n",
      "1343 1458\n",
      "1344 641\n",
      "1345 2620\n",
      "1346 10925\n",
      "1347 480\n",
      "1348 1861\n",
      "1349 1360\n",
      "1350 2001\n",
      "1351 884\n",
      "1352 3633\n",
      "1353 175\n",
      "1354 432\n",
      "1355 2607\n",
      "1356 989\n",
      "1357 338\n",
      "1358 141\n",
      "1359 61\n",
      "1360 3398\n",
      "1361 3585\n",
      "1362 1715\n",
      "1363 5448\n",
      "1364 191\n",
      "1365 270\n",
      "1366 1149\n",
      "1367 1481\n",
      "1368 146\n",
      "1369 134\n",
      "1370 7461\n",
      "1371 3748\n",
      "1372 1149\n",
      "1373 368\n",
      "1374 1945\n",
      "1375 452\n",
      "1376 543\n",
      "1377 512\n",
      "1378 3106\n",
      "1379 980\n",
      "1380 529\n",
      "1381 2561\n",
      "1382 405\n",
      "1383 1067\n",
      "1384 421\n",
      "1385 2146\n",
      "1386 1471\n",
      "1387 563\n",
      "1388 140\n",
      "1389 12\n",
      "1390 640\n",
      "1391 228\n",
      "1392 161\n",
      "1393 2117\n",
      "1394 1918\n",
      "1395 7817\n",
      "1396 1947\n",
      "1397 2291\n",
      "1398 421\n",
      "1399 430\n",
      "1400 3417\n",
      "1401 765\n",
      "1402 188\n",
      "1403 1424\n",
      "1404 504\n",
      "1405 1465\n",
      "1406 296\n",
      "1407 7621\n",
      "1408 5669\n",
      "1409 433\n",
      "1410 760\n",
      "1411 9127\n",
      "1412 12756\n",
      "1413 1337\n",
      "1414 163\n",
      "1415 8900\n",
      "1416 2369\n",
      "1417 10983\n",
      "1418 657\n",
      "1419 7665\n",
      "1420 329\n",
      "1421 1551\n",
      "1422 2247\n",
      "1423 663\n",
      "1424 327\n",
      "1425 1005\n",
      "1426 2509\n",
      "1427 20704\n",
      "1428 736\n",
      "1429 1088\n",
      "1430 618\n",
      "1431 288\n",
      "1432 2341\n",
      "1433 892\n",
      "1434 126\n",
      "1435 260\n",
      "1436 716\n",
      "1437 481\n",
      "1438 3155\n",
      "1439 460\n",
      "1440 1199\n",
      "1441 511\n",
      "1442 92\n",
      "1443 130\n",
      "1444 210\n",
      "1445 942\n",
      "1446 3518\n",
      "1447 1089\n",
      "1448 3255\n",
      "1449 2623\n",
      "1450 1174\n",
      "1451 308\n",
      "1452 897\n",
      "1453 1340\n",
      "1454 2198\n",
      "1455 879\n",
      "1456 858\n",
      "1457 1927\n",
      "1458 4729\n",
      "1459 1503\n",
      "1460 489\n",
      "1461 45\n",
      "1462 1951\n",
      "1463 182\n",
      "1464 572\n",
      "1465 715\n",
      "1466 1178\n",
      "1467 5921\n",
      "1468 475\n",
      "1469 380\n",
      "1470 87\n",
      "1471 290\n",
      "1472 501\n",
      "1473 2483\n",
      "1474 699\n",
      "1475 720\n",
      "1476 851\n",
      "1477 4478\n",
      "1478 4638\n",
      "1479 159\n",
      "1480 82\n",
      "1481 118\n",
      "1482 261\n",
      "1483 924\n",
      "1484 598\n",
      "1485 1674\n",
      "1486 533\n",
      "1487 4268\n",
      "1488 996\n",
      "1489 364\n",
      "1490 701\n",
      "1491 438\n",
      "1492 825\n",
      "1493 1616\n",
      "1494 501\n",
      "1495 973\n",
      "1496 892\n",
      "1497 630\n",
      "1498 4014\n",
      "1499 349\n",
      "1500 1881\n",
      "1501 2362\n",
      "1502 3762\n",
      "1503 611\n",
      "1504 2194\n",
      "1505 629\n",
      "1506 1373\n",
      "1507 6181\n",
      "1508 717\n",
      "1509 90\n",
      "1510 790\n",
      "1511 761\n",
      "1512 6099\n",
      "1513 3243\n",
      "1514 287\n",
      "1515 13426\n",
      "1516 4091\n",
      "1517 1074\n",
      "1518 2228\n",
      "1519 693\n",
      "1520 728\n",
      "1521 1823\n",
      "1522 3753\n",
      "1523 935\n",
      "1524 2540\n",
      "1525 2075\n",
      "1526 5037\n",
      "1527 1611\n",
      "1528 881\n",
      "1529 4404\n",
      "1530 615\n",
      "1531 6974\n",
      "1532 460\n",
      "1533 607\n",
      "1534 4372\n",
      "1535 2328\n",
      "1536 904\n",
      "1537 490\n",
      "1538 475\n",
      "1539 1078\n",
      "1540 2472\n",
      "1541 1697\n",
      "1542 326\n",
      "1543 770\n",
      "1544 2536\n",
      "1545 463\n",
      "1546 2901\n",
      "1547 559\n",
      "1548 21427\n",
      "1549 244\n",
      "1550 1133\n",
      "1551 1129\n",
      "1552 35\n",
      "1553 2486\n",
      "1554 1868\n",
      "1555 1418\n",
      "1556 2572\n",
      "1557 1527\n",
      "1558 8347\n",
      "1559 770\n",
      "1560 2384\n",
      "1561 2655\n",
      "1562 694\n",
      "1563 1981\n",
      "1564 555\n",
      "1565 929\n",
      "1566 350\n",
      "1567 416\n",
      "1568 444\n",
      "1569 1573\n",
      "1570 955\n",
      "1571 2372\n",
      "1572 1042\n",
      "1573 8073\n",
      "1574 742\n",
      "1575 502\n",
      "1576 3547\n",
      "1577 388\n",
      "1578 582\n",
      "1579 881\n",
      "1580 3630\n",
      "1581 395\n",
      "1582 2319\n",
      "1583 2522\n",
      "1584 1035\n",
      "1585 3056\n",
      "1586 339\n",
      "1587 2814\n",
      "1588 1120\n",
      "1589 1132\n",
      "1590 15724\n",
      "1591 322\n",
      "1592 539\n",
      "1593 615\n",
      "1594 6209\n",
      "1595 6165\n",
      "1596 1923\n",
      "1597 155\n",
      "1598 350\n",
      "1599 839\n",
      "1600 1432\n",
      "1601 437\n",
      "1602 1724\n",
      "1603 5334\n",
      "1604 1499\n",
      "1605 203\n",
      "1606 741\n",
      "1607 2124\n",
      "1608 2161\n",
      "1609 4155\n",
      "1610 3355\n",
      "1611 1203\n",
      "1612 748\n",
      "1613 618\n",
      "1614 989\n",
      "1615 1123\n",
      "1616 1116\n",
      "1617 213\n",
      "1618 2508\n",
      "1619 2557\n",
      "1620 679\n",
      "1621 3322\n",
      "1622 286\n",
      "1623 1139\n",
      "1624 623\n",
      "1625 2531\n",
      "1626 2964\n",
      "1627 2247\n",
      "1628 1860\n",
      "1629 75\n",
      "1630 69\n",
      "1631 1233\n",
      "1632 2967\n",
      "1633 3728\n",
      "1634 1365\n",
      "1635 599\n",
      "1636 655\n",
      "1637 252\n",
      "1638 277\n",
      "1639 1296\n",
      "1640 2817\n",
      "1641 665\n",
      "1642 2263\n",
      "1643 66\n",
      "1644 174\n",
      "1645 275\n",
      "1646 812\n",
      "1647 2514\n",
      "1648 3295\n",
      "1649 2161\n",
      "1650 2725\n",
      "1651 4122\n",
      "1652 2416\n",
      "1653 1502\n",
      "1654 7626\n",
      "1655 141\n",
      "1656 3415\n",
      "1657 9332\n",
      "1658 9\n",
      "1659 9291\n",
      "1660 4191\n",
      "1661 88\n",
      "1662 8680\n",
      "1663 11\n",
      "1664 684\n",
      "1665 278\n",
      "1666 794\n",
      "1667 11955\n",
      "1668 16888\n",
      "1669 239\n",
      "1670 1582\n",
      "1671 2796\n",
      "1672 1137\n",
      "1673 1078\n",
      "1674 1079\n",
      "1675 1575\n",
      "1676 942\n",
      "1677 165\n",
      "1678 640\n",
      "1679 1426\n",
      "1680 1177\n",
      "1681 1474\n",
      "1682 628\n",
      "1683 1038\n",
      "1684 647\n",
      "1685 1361\n",
      "1686 3558\n",
      "1687 1728\n",
      "1688 7272\n",
      "1689 1017\n",
      "1690 963\n",
      "1691 184\n",
      "1692 16\n",
      "1693 463\n",
      "1694 5861\n",
      "1695 2520\n",
      "1696 2492\n",
      "1697 377\n",
      "1698 2074\n",
      "1699 463\n",
      "1700 492\n",
      "1701 2572\n",
      "1702 272\n",
      "1703 4227\n",
      "1704 1390\n",
      "1705 3665\n",
      "1706 8263\n",
      "1707 695\n",
      "1708 3015\n",
      "1709 798\n",
      "1710 235\n",
      "1711 162\n",
      "1712 1024\n",
      "1713 147\n",
      "1714 3405\n",
      "1715 818\n",
      "1716 328\n",
      "1717 2267\n",
      "1718 366\n",
      "1719 2647\n",
      "1720 286\n",
      "1721 1402\n",
      "1722 247\n",
      "1723 1993\n",
      "1724 3098\n",
      "1725 261\n",
      "1726 342\n",
      "1727 1686\n",
      "1728 1387\n",
      "1729 2794\n",
      "1730 2281\n",
      "1731 833\n",
      "1732 383\n",
      "1733 388\n",
      "1734 1036\n",
      "1735 473\n",
      "1736 668\n",
      "1737 166\n",
      "1738 2274\n",
      "1739 2460\n",
      "1740 1387\n",
      "1741 1812\n",
      "1742 15743\n",
      "1743 1208\n",
      "1744 25487\n",
      "1745 1763\n",
      "1746 13929\n",
      "1747 5100\n",
      "1748 1560\n",
      "1749 1919\n",
      "1750 5396\n",
      "1751 1222\n",
      "1752 395\n",
      "1753 133\n",
      "1754 3648\n",
      "1755 15167\n",
      "1756 15152\n",
      "1757 1471\n",
      "1758 829\n",
      "1759 1849\n",
      "1760 663\n",
      "1761 8285\n",
      "1762 5202\n",
      "1763 912\n",
      "1764 489\n",
      "1765 749\n",
      "1766 337\n",
      "1767 678\n",
      "1768 790\n",
      "1769 5448\n",
      "1770 1462\n",
      "1771 1224\n",
      "1772 460\n",
      "1773 2607\n",
      "1774 65\n",
      "1775 108\n",
      "1776 37\n",
      "1777 1434\n",
      "1778 3100\n",
      "1779 387\n",
      "1780 2524\n",
      "1781 553\n",
      "1782 277\n",
      "1783 2108\n",
      "1784 6082\n",
      "1785 741\n",
      "1786 1901\n",
      "1787 359\n",
      "1788 1283\n",
      "1789 162\n",
      "1790 823\n",
      "1791 916\n",
      "1792 1609\n",
      "1793 275\n",
      "1794 815\n",
      "1795 1047\n",
      "1796 444\n",
      "1797 5668\n",
      "1798 1128\n",
      "1799 3217\n",
      "1800 4897\n",
      "1801 4605\n",
      "1802 3253\n",
      "1803 3380\n",
      "1804 159\n",
      "1805 4449\n",
      "1806 1590\n",
      "1807 310\n",
      "1808 3356\n",
      "1809 2741\n",
      "1810 254\n",
      "1811 1326\n",
      "1812 345\n",
      "1813 371\n",
      "1814 1034\n",
      "1815 593\n",
      "1816 428\n",
      "1817 326\n",
      "1818 711\n",
      "1819 574\n",
      "1820 1136\n",
      "1821 499\n",
      "1822 2166\n",
      "1823 984\n",
      "1824 1339\n",
      "1825 311\n",
      "1826 1898\n",
      "1827 7960\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1828 794\n",
      "1829 2331\n",
      "1830 39\n",
      "1831 2930\n",
      "1832 439\n",
      "1833 3087\n",
      "1834 375\n",
      "1835 332\n",
      "1836 39\n",
      "1837 519\n",
      "1838 994\n",
      "1839 1736\n",
      "1840 26289\n",
      "1841 751\n",
      "1842 253\n",
      "1843 585\n",
      "1844 708\n",
      "1845 479\n",
      "1846 1915\n",
      "1847 1969\n",
      "1848 1551\n",
      "1849 2599\n",
      "1850 688\n",
      "1851 713\n",
      "1852 1792\n",
      "1853 796\n",
      "1854 9323\n",
      "1855 1783\n",
      "1856 2207\n",
      "1857 817\n",
      "1858 471\n",
      "1859 12356\n",
      "1860 879\n",
      "1861 415\n",
      "1862 1198\n",
      "1863 1146\n",
      "1864 228\n",
      "1865 1308\n",
      "1866 1014\n",
      "1867 774\n",
      "1868 704\n",
      "1869 1340\n",
      "1870 734\n",
      "1871 1560\n",
      "1872 4784\n",
      "1873 1695\n",
      "1874 1209\n",
      "1875 307\n",
      "1876 331\n",
      "1877 2290\n",
      "1878 142\n",
      "1879 3053\n",
      "1880 565\n",
      "1881 1062\n",
      "1882 502\n",
      "1883 2878\n",
      "1884 1602\n",
      "1885 733\n",
      "1886 273\n",
      "1887 2920\n",
      "1888 2710\n",
      "1889 14050\n",
      "1890 621\n",
      "1891 164\n",
      "1892 991\n",
      "1893 677\n",
      "1894 1876\n",
      "1895 1748\n",
      "1896 1378\n",
      "1897 11282\n",
      "1898 325\n",
      "1899 651\n",
      "1900 780\n",
      "1901 812\n",
      "1902 211\n",
      "1903 162\n",
      "1904 3338\n",
      "1905 53\n",
      "1906 1511\n",
      "1907 1295\n",
      "1908 2387\n",
      "1909 2841\n",
      "1910 1542\n",
      "1911 20385\n",
      "1912 374\n",
      "1913 768\n",
      "1914 392\n",
      "1915 690\n",
      "1916 2194\n",
      "1917 272\n",
      "1918 742\n",
      "1919 628\n",
      "1920 2983\n",
      "1921 406\n",
      "1922 1067\n",
      "1923 3410\n",
      "1924 394\n",
      "1925 1181\n",
      "1926 3834\n",
      "1927 1732\n",
      "1928 748\n",
      "1929 4739\n",
      "1930 5734\n",
      "1931 102\n",
      "1932 1411\n",
      "1933 394\n",
      "1934 2428\n",
      "1935 398\n",
      "1936 20081\n",
      "1937 385\n",
      "1938 10560\n",
      "1939 820\n",
      "1940 201\n",
      "1941 571\n",
      "1942 15265\n",
      "1943 609\n",
      "1944 1049\n",
      "1945 1431\n",
      "1946 1834\n",
      "1947 1169\n",
      "1948 899\n",
      "1949 129\n",
      "1950 409\n",
      "1951 18840\n",
      "1952 999\n",
      "1953 1997\n",
      "1954 1283\n",
      "1955 121\n",
      "1956 1548\n",
      "1957 5172\n",
      "1958 2461\n",
      "1959 2327\n",
      "1960 4965\n",
      "1961 290\n",
      "1962 869\n",
      "1963 2260\n",
      "1964 1294\n",
      "1965 435\n",
      "1966 627\n",
      "1967 1066\n",
      "1968 298\n",
      "1969 617\n",
      "1970 4532\n",
      "1971 484\n",
      "1972 43\n",
      "1973 980\n",
      "1974 189\n",
      "1975 852\n",
      "1976 2115\n",
      "1977 4234\n",
      "1978 2046\n",
      "1979 1264\n",
      "1980 937\n",
      "1981 335\n",
      "1982 1673\n",
      "1983 4382\n",
      "1984 759\n",
      "1985 434\n",
      "1986 764\n",
      "1987 533\n",
      "1988 357\n",
      "1989 877\n",
      "1990 174\n",
      "1991 70\n",
      "1992 780\n",
      "1993 1184\n",
      "1994 3855\n",
      "1995 1774\n",
      "1996 1589\n",
      "1997 1251\n",
      "1998 250\n",
      "1999 7018\n",
      "2000 1668\n",
      "2001 128\n",
      "2002 671\n",
      "2003 3788\n",
      "2004 10780\n",
      "2005 1178\n",
      "2006 1674\n",
      "2007 322\n",
      "2008 1115\n",
      "2009 391\n",
      "2010 3407\n",
      "2011 6397\n",
      "2012 2943\n",
      "2013 887\n",
      "2014 1633\n",
      "2015 736\n",
      "2016 1460\n",
      "2017 389\n",
      "2018 1300\n",
      "2019 2985\n",
      "2020 2971\n",
      "2021 2491\n",
      "2022 666\n",
      "2023 242\n",
      "2024 733\n",
      "2025 4208\n",
      "2026 3455\n",
      "2027 966\n",
      "2028 344\n",
      "2029 713\n",
      "2030 540\n",
      "2031 1047\n",
      "2032 12686\n",
      "2033 1802\n",
      "2034 348\n",
      "2035 218\n",
      "2036 1817\n",
      "2037 1217\n",
      "2038 3511\n",
      "2039 1647\n",
      "2040 492\n",
      "2041 1977\n",
      "2042 5091\n",
      "2043 14111\n",
      "2044 317\n",
      "2045 2121\n",
      "2046 510\n",
      "2047 616\n",
      "2048 1551\n",
      "2049 1413\n",
      "2050 152\n",
      "2051 282\n",
      "2052 598\n",
      "2053 1045\n",
      "2054 362\n",
      "2055 2473\n",
      "2056 614\n",
      "2057 7528\n",
      "2058 850\n",
      "2059 358\n",
      "2060 313\n",
      "2061 1236\n",
      "2062 2298\n",
      "2063 1625\n",
      "2064 1938\n",
      "2065 165\n",
      "2066 3666\n",
      "2067 585\n",
      "2068 7786\n",
      "2069 616\n",
      "2070 859\n",
      "2071 1029\n",
      "2072 1290\n",
      "2073 610\n",
      "2074 58\n",
      "2075 5811\n",
      "2076 9786\n",
      "2077 310\n",
      "2078 162\n",
      "2079 996\n",
      "2080 141\n",
      "2081 297\n",
      "2082 1982\n",
      "2083 1946\n",
      "2084 200\n",
      "2085 2547\n",
      "2086 5799\n",
      "2087 6159\n",
      "2088 2711\n",
      "2089 265\n",
      "2090 677\n",
      "2091 162\n",
      "2092 1123\n",
      "2093 335\n",
      "2094 105\n",
      "2095 1360\n",
      "2096 20333\n",
      "2097 1728\n",
      "2098 1282\n",
      "2099 566\n",
      "2100 648\n",
      "2101 262\n",
      "2102 7347\n",
      "2103 1219\n",
      "2104 1855\n",
      "2105 588\n",
      "2106 344\n",
      "2107 719\n",
      "2108 371\n",
      "2109 357\n",
      "2110 1967\n",
      "2111 15978\n",
      "2112 255\n",
      "2113 68\n",
      "2114 167\n",
      "2115 416\n",
      "2116 2724\n",
      "2117 3225\n",
      "2118 1141\n",
      "2119 108\n",
      "2120 4558\n",
      "2121 188\n",
      "2122 180\n",
      "2123 173\n",
      "2124 911\n",
      "2125 2673\n",
      "2126 11106\n",
      "2127 1788\n",
      "2128 3950\n",
      "2129 1363\n",
      "2130 4112\n",
      "2131 478\n",
      "2132 2593\n",
      "2133 2513\n",
      "2134 2026\n",
      "2135 1458\n",
      "2136 2738\n",
      "2137 1536\n",
      "2138 1368\n",
      "2139 679\n",
      "2140 2210\n",
      "2141 19506\n",
      "2142 2967\n",
      "2143 487\n",
      "2144 1600\n",
      "2145 402\n",
      "2146 3243\n",
      "2147 7732\n",
      "2148 365\n",
      "2149 86\n",
      "2150 7501\n",
      "2151 430\n",
      "2152 2492\n",
      "2153 4412\n",
      "2154 539\n",
      "2155 198\n",
      "2156 8139\n",
      "2157 11237\n",
      "2158 2352\n",
      "2159 566\n",
      "2160 1325\n",
      "2161 469\n",
      "2162 3246\n",
      "2163 1078\n",
      "2164 294\n",
      "2165 541\n",
      "2166 1322\n",
      "2167 136\n",
      "2168 549\n",
      "2169 2676\n",
      "2170 3256\n",
      "2171 2740\n",
      "2172 3199\n",
      "2173 476\n",
      "2174 5399\n",
      "2175 3197\n",
      "2176 410\n",
      "2177 2299\n",
      "2178 3986\n",
      "2179 1999\n",
      "2180 1108\n",
      "2181 2819\n",
      "2182 2545\n",
      "2183 13710\n",
      "2184 1556\n",
      "2185 1973\n",
      "2186 858\n",
      "2187 943\n",
      "2188 709\n",
      "2189 3268\n",
      "2190 162\n",
      "2191 910\n",
      "2192 1588\n",
      "2193 6132\n",
      "2194 2013\n",
      "2195 1301\n",
      "2196 3236\n",
      "2197 356\n",
      "2198 2425\n",
      "2199 758\n",
      "2200 1564\n",
      "2201 5517\n",
      "2202 1177\n",
      "2203 158\n",
      "2204 181\n",
      "2205 5049\n",
      "2206 144\n",
      "2207 562\n",
      "2208 3436\n",
      "2209 887\n",
      "2210 7296\n",
      "2211 2571\n",
      "2212 517\n",
      "2213 2767\n",
      "2214 712\n",
      "2215 3176\n",
      "2216 592\n",
      "2217 2435\n",
      "2218 844\n",
      "2219 10745\n",
      "2220 17430\n",
      "2221 3497\n",
      "2222 315\n",
      "2223 159\n",
      "2224 648\n",
      "2225 888\n",
      "2226 1487\n",
      "2227 53\n",
      "2228 195\n",
      "2229 15808\n",
      "2230 3248\n",
      "2231 2560\n",
      "2232 1662\n",
      "2233 1132\n",
      "2234 3383\n",
      "2235 2819\n",
      "2236 7728\n",
      "2237 865\n",
      "2238 1959\n",
      "2239 447\n",
      "2240 5760\n",
      "2241 2154\n",
      "2242 2206\n",
      "2243 3551\n",
      "2244 322\n",
      "2245 885\n",
      "2246 231\n",
      "2247 539\n",
      "2248 2800\n",
      "2249 255\n",
      "2250 274\n",
      "2251 295\n",
      "2252 2824\n",
      "2253 934\n",
      "2254 1367\n",
      "2255 1273\n",
      "2256 660\n",
      "2257 16458\n",
      "2258 10602\n",
      "2259 251\n",
      "2260 146\n",
      "2261 301\n",
      "2262 443\n",
      "2263 734\n",
      "2264 231\n",
      "2265 241\n",
      "2266 12\n",
      "2267 256\n",
      "2268 199\n",
      "2269 1161\n",
      "2270 2801\n",
      "2271 1119\n",
      "2272 3050\n",
      "2273 469\n",
      "2274 288\n",
      "2275 1133\n",
      "2276 1754\n",
      "2277 690\n",
      "2278 533\n",
      "2279 415\n",
      "2280 379\n",
      "2281 956\n",
      "2282 877\n",
      "2283 623\n",
      "2284 847\n",
      "2285 7801\n",
      "2286 2453\n",
      "2287 3458\n",
      "2288 47\n",
      "2289 663\n",
      "2290 448\n",
      "2291 748\n",
      "2292 1961\n",
      "2293 335\n",
      "2294 246\n",
      "2295 1045\n",
      "2296 13\n",
      "2297 683\n",
      "2298 367\n",
      "2299 930\n",
      "2300 440\n",
      "2301 934\n",
      "2302 377\n",
      "2303 1708\n",
      "2304 5128\n",
      "2305 2650\n",
      "2306 495\n",
      "2307 543\n",
      "2308 982\n",
      "2309 2233\n",
      "2310 1452\n",
      "2311 307\n",
      "2312 4500\n",
      "2313 2353\n",
      "2314 3372\n",
      "2315 1487\n",
      "2316 4938\n",
      "2317 290\n",
      "2318 783\n",
      "2319 649\n",
      "2320 197\n",
      "2321 1921\n",
      "2322 3708\n",
      "2323 4276\n",
      "2324 4498\n",
      "2325 1810\n",
      "2326 1505\n",
      "2327 412\n",
      "2328 327\n",
      "2329 49\n",
      "2330 631\n",
      "2331 1475\n",
      "2332 715\n",
      "2333 974\n",
      "2334 880\n",
      "2335 5462\n",
      "2336 433\n",
      "2337 3288\n",
      "2338 278\n",
      "2339 739\n",
      "2340 788\n",
      "2341 163\n",
      "2342 1704\n",
      "2343 3353\n",
      "2344 2770\n",
      "2345 2351\n",
      "2346 1146\n",
      "2347 1060\n",
      "2348 620\n",
      "2349 242\n",
      "2350 649\n",
      "2351 1140\n",
      "2352 182\n",
      "2353 1795\n",
      "2354 212\n",
      "2355 11391\n",
      "2356 892\n",
      "2357 341\n",
      "2358 11887\n",
      "2359 1556\n",
      "2360 486\n",
      "2361 3156\n",
      "2362 176\n",
      "2363 2456\n",
      "2364 433\n",
      "2365 321\n",
      "2366 2674\n",
      "2367 2615\n",
      "2368 24280\n",
      "2369 413\n",
      "2370 475\n",
      "2371 1371\n",
      "2372 478\n",
      "2373 127\n",
      "2374 1541\n",
      "2375 433\n",
      "2376 3868\n",
      "2377 2514\n",
      "2378 5480\n",
      "2379 374\n",
      "2380 2819\n",
      "2381 562\n",
      "2382 627\n",
      "2383 334\n",
      "2384 280\n",
      "2385 2364\n",
      "2386 1315\n",
      "2387 210\n",
      "2388 372\n",
      "2389 1315\n",
      "2390 2091\n",
      "2391 535\n",
      "2392 5953\n",
      "2393 1648\n",
      "2394 572\n",
      "2395 7477\n",
      "2396 4783\n",
      "2397 1439\n",
      "2398 2981\n",
      "2399 2039\n",
      "2400 7707\n",
      "2401 2115\n",
      "2402 958\n",
      "2403 1563\n",
      "2404 6161\n",
      "2405 1109\n",
      "2406 251\n",
      "2407 2149\n",
      "2408 792\n",
      "2409 3250\n",
      "2410 342\n",
      "2411 453\n",
      "2412 982\n",
      "2413 1060\n",
      "2414 2122\n",
      "2415 980\n",
      "2416 15052\n",
      "2417 6836\n",
      "2418 1425\n",
      "2419 1102\n",
      "2420 1128\n",
      "2421 380\n",
      "2422 1577\n",
      "2423 1728\n",
      "2424 2074\n",
      "2425 780\n",
      "2426 615\n",
      "2427 875\n",
      "2428 286\n",
      "2429 2188\n",
      "2430 328\n",
      "2431 680\n",
      "2432 219\n",
      "2433 520\n",
      "2434 7329\n",
      "2435 1758\n",
      "2436 508\n",
      "2437 1288\n",
      "2438 203\n",
      "2439 557\n",
      "2440 998\n",
      "2441 449\n",
      "2442 562\n",
      "2443 4614\n",
      "2444 133\n",
      "2445 1860\n",
      "2446 1115\n",
      "2447 851\n",
      "2448 4467\n",
      "2449 8436\n",
      "2450 2533\n",
      "2451 8003\n",
      "2452 1679\n",
      "2453 2008\n",
      "2454 1129\n",
      "2455 1002\n",
      "2456 1475\n",
      "2457 1488\n",
      "2458 1273\n",
      "2459 1142\n",
      "2460 114\n",
      "2461 2627\n",
      "2462 756\n",
      "2463 3118\n",
      "2464 4020\n",
      "2465 485\n",
      "2466 597\n",
      "2467 1825\n",
      "2468 598\n",
      "2469 969\n",
      "2470 101\n",
      "2471 313\n",
      "2472 8028\n",
      "2473 1236\n",
      "2474 1804\n",
      "2475 273\n",
      "2476 3270\n",
      "2477 1282\n",
      "2478 1032\n",
      "2479 22373\n",
      "2480 14462\n",
      "2481 440\n",
      "2482 2108\n",
      "2483 5024\n",
      "2484 16398\n",
      "2485 201\n",
      "2486 8589\n",
      "2487 1822\n",
      "2488 22921\n",
      "2489 256\n",
      "2490 336\n",
      "2491 822\n",
      "2492 5350\n",
      "2493 2333\n",
      "2494 1606\n",
      "2495 5799\n",
      "2496 142\n",
      "2497 407\n",
      "2498 620\n",
      "2499 420\n",
      "2500 711\n",
      "2501 456\n",
      "2502 508\n",
      "2503 914\n",
      "2504 337\n",
      "2505 1068\n",
      "2506 3984\n",
      "2507 1612\n",
      "2508 972\n",
      "2509 416\n",
      "2510 341\n",
      "2511 334\n",
      "2512 1026\n",
      "2513 424\n",
      "2514 3023\n",
      "2515 368\n",
      "2516 755\n",
      "2517 3267\n",
      "2518 450\n",
      "2519 2891\n",
      "2520 2028\n",
      "2521 929\n",
      "2522 1347\n",
      "2523 2100\n",
      "2524 2136\n",
      "2525 1245\n",
      "2526 884\n",
      "2527 10019\n",
      "2528 868\n",
      "2529 1577\n",
      "2530 365\n",
      "2531 126\n",
      "2532 20235\n",
      "2533 487\n",
      "2534 620\n",
      "2535 2351\n",
      "2536 427\n",
      "2537 427\n",
      "2538 8395\n",
      "2539 960\n",
      "2540 1606\n",
      "2541 466\n",
      "2542 695\n",
      "2543 76\n",
      "2544 1857\n",
      "2545 848\n",
      "2546 1238\n",
      "2547 3129\n",
      "2548 2841\n",
      "2549 38\n",
      "2550 1078\n",
      "2551 16633\n",
      "2552 1408\n",
      "2553 2395\n",
      "2554 708\n",
      "2555 112\n",
      "2556 10412\n",
      "2557 2231\n",
      "2558 1317\n",
      "2559 168\n",
      "2560 862\n",
      "2561 4918\n",
      "2562 858\n",
      "2563 738\n",
      "2564 684\n",
      "2565 487\n",
      "2566 5526\n",
      "2567 1047\n",
      "2568 1001\n",
      "2569 2548\n",
      "2570 1542\n",
      "2571 1370\n",
      "2572 4751\n",
      "2573 69\n",
      "2574 574\n",
      "2575 425\n",
      "2576 527\n",
      "2577 2546\n",
      "2578 522\n",
      "2579 981\n",
      "2580 455\n",
      "2581 565\n",
      "2582 121\n",
      "2583 6522\n",
      "2584 137\n",
      "2585 477\n",
      "2586 1093\n",
      "2587 316\n",
      "2588 899\n",
      "2589 2239\n",
      "2590 5399\n",
      "2591 363\n",
      "2592 2032\n",
      "2593 1293\n",
      "2594 235\n",
      "2595 323\n",
      "2596 765\n",
      "2597 8992\n",
      "2598 1483\n",
      "2599 348\n",
      "2600 443\n",
      "2601 453\n",
      "2602 426\n",
      "2603 433\n",
      "2604 631\n",
      "2605 626\n",
      "2606 907\n",
      "2607 4221\n",
      "2608 251\n",
      "2609 481\n",
      "2610 2664\n",
      "2611 6393\n",
      "2612 112\n",
      "2613 19971\n",
      "2614 7088\n",
      "2615 4861\n",
      "2616 2038\n",
      "2617 1431\n",
      "2618 1125\n",
      "2619 862\n",
      "2620 123\n",
      "2621 5782\n",
      "2622 515\n",
      "2623 1092\n",
      "2624 7331\n",
      "2625 9300\n",
      "2626 7056\n",
      "2627 889\n",
      "2628 11407\n",
      "2629 1215\n",
      "2630 1882\n",
      "2631 322\n",
      "2632 1540\n",
      "2633 3474\n",
      "2634 767\n",
      "2635 625\n",
      "2636 708\n",
      "2637 360\n",
      "2638 426\n",
      "2639 487\n",
      "2640 2765\n",
      "2641 20921\n",
      "2642 513\n",
      "2643 1153\n",
      "2644 384\n",
      "2645 1423\n",
      "2646 465\n",
      "2647 280\n",
      "2648 7992\n",
      "2649 987\n",
      "2650 3409\n",
      "2651 2643\n",
      "2652 658\n",
      "2653 12029\n",
      "2654 2820\n",
      "2655 1760\n",
      "2656 373\n",
      "2657 412\n",
      "2658 100\n",
      "2659 1087\n",
      "2660 1865\n",
      "2661 65\n",
      "2662 1646\n",
      "2663 2194\n",
      "2664 669\n",
      "2665 1268\n",
      "2666 1314\n",
      "2667 1169\n",
      "2668 505\n",
      "2669 484\n",
      "2670 415\n",
      "2671 532\n",
      "2672 640\n",
      "2673 599\n",
      "2674 51\n",
      "2675 759\n",
      "2676 100\n",
      "2677 362\n",
      "2678 899\n",
      "2679 861\n",
      "2680 692\n",
      "2681 894\n",
      "2682 1586\n",
      "2683 966\n",
      "2684 1296\n",
      "2685 1143\n",
      "2686 1909\n",
      "2687 2500\n",
      "2688 1427\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2689 897\n",
      "2690 2423\n",
      "2691 1383\n",
      "2692 46\n",
      "2693 1249\n",
      "2694 348\n",
      "2695 1755\n",
      "2696 1461\n",
      "2697 289\n",
      "2698 716\n",
      "2699 954\n",
      "2700 2081\n",
      "2701 759\n",
      "2702 2300\n",
      "2703 907\n",
      "2704 2192\n",
      "2705 1087\n",
      "2706 2440\n",
      "2707 1128\n",
      "2708 785\n",
      "2709 1039\n",
      "2710 1139\n",
      "2711 1014\n",
      "2712 1114\n",
      "2713 1001\n",
      "2714 413\n",
      "2715 2154\n",
      "2716 2221\n",
      "2717 747\n",
      "2718 1170\n",
      "2719 2118\n",
      "2720 2141\n",
      "2721 1093\n",
      "2722 18724\n",
      "2723 2771\n",
      "2724 4990\n",
      "2725 219\n",
      "2726 352\n",
      "2727 6812\n",
      "2728 2373\n",
      "2729 729\n",
      "2730 16819\n",
      "2731 4768\n",
      "2732 1286\n",
      "2733 731\n",
      "2734 425\n",
      "2735 1091\n",
      "2736 21570\n",
      "2737 6478\n",
      "2738 919\n",
      "2739 8419\n",
      "2740 3252\n",
      "2741 4918\n",
      "2742 6415\n",
      "2743 14292\n",
      "2744 17813\n",
      "2745 2825\n",
      "2746 991\n",
      "2747 1035\n",
      "2748 2250\n",
      "2749 733\n",
      "2750 1837\n",
      "2751 8032\n",
      "2752 1056\n",
      "2753 1504\n",
      "2754 1043\n",
      "2755 1014\n",
      "2756 515\n",
      "2757 244\n",
      "2758 113\n",
      "2759 587\n",
      "2760 577\n",
      "2761 618\n",
      "2762 926\n",
      "2763 1096\n",
      "2764 719\n",
      "2765 2023\n",
      "2766 832\n",
      "2767 3046\n",
      "2768 414\n",
      "2769 158\n",
      "2770 3834\n",
      "2771 2888\n",
      "2772 359\n",
      "2773 1589\n",
      "2774 209\n",
      "2775 5405\n",
      "2776 1161\n",
      "2777 464\n",
      "2778 1344\n",
      "2779 1520\n",
      "2780 1515\n",
      "2781 301\n",
      "2782 2374\n",
      "2783 619\n",
      "2784 307\n",
      "2785 1650\n",
      "2786 1101\n",
      "2787 1301\n",
      "2788 1369\n",
      "2789 1380\n",
      "2790 1257\n",
      "2791 1716\n",
      "2792 1877\n",
      "2793 526\n",
      "2794 1041\n",
      "2795 263\n",
      "2796 1040\n",
      "2797 716\n",
      "2798 746\n",
      "2799 779\n",
      "2800 2607\n",
      "2801 2701\n",
      "2802 614\n",
      "2803 712\n",
      "2804 1240\n",
      "2805 766\n",
      "2806 1688\n",
      "2807 368\n",
      "2808 586\n",
      "2809 1563\n",
      "2810 613\n",
      "2811 345\n",
      "2812 3595\n",
      "2813 985\n",
      "2814 1815\n",
      "2815 2339\n",
      "2816 630\n",
      "2817 275\n",
      "2818 2428\n",
      "2819 4307\n",
      "2820 3153\n",
      "2821 548\n",
      "2822 5366\n",
      "2823 305\n",
      "2824 5798\n",
      "2825 289\n",
      "2826 4654\n",
      "2827 226\n",
      "2828 2176\n",
      "2829 14085\n",
      "2830 3582\n",
      "2831 444\n",
      "2832 298\n",
      "2833 473\n",
      "2834 2042\n",
      "2835 3958\n",
      "2836 877\n",
      "2837 355\n",
      "2838 7199\n",
      "2839 936\n",
      "2840 286\n",
      "2841 283\n",
      "2842 3472\n",
      "2843 338\n",
      "2844 2134\n",
      "2845 6047\n",
      "2846 2215\n",
      "2847 1616\n",
      "2848 2634\n",
      "2849 1474\n",
      "2850 336\n",
      "2851 469\n",
      "2852 364\n",
      "2853 237\n",
      "2854 248\n",
      "2855 957\n",
      "2856 2386\n",
      "2857 1244\n",
      "2858 13779\n",
      "2859 2676\n",
      "2860 303\n",
      "2861 931\n",
      "2862 241\n",
      "2863 475\n",
      "2864 906\n",
      "2865 123\n",
      "2866 2004\n",
      "2867 961\n",
      "2868 1788\n",
      "2869 176\n",
      "2870 1105\n",
      "2871 5464\n",
      "2872 1353\n",
      "2873 1525\n",
      "2874 1990\n",
      "2875 2063\n",
      "2876 1441\n",
      "2877 1252\n",
      "2878 2572\n",
      "2879 1412\n",
      "2880 363\n",
      "2881 3305\n",
      "2882 2097\n",
      "2883 89\n",
      "2884 2879\n",
      "2885 375\n",
      "2886 1877\n",
      "2887 616\n",
      "2888 3795\n",
      "2889 2620\n",
      "2890 10208\n",
      "2891 141\n",
      "2892 2730\n",
      "2893 504\n",
      "2894 1060\n",
      "2895 2857\n",
      "2896 556\n",
      "2897 1642\n",
      "2898 372\n",
      "2899 353\n",
      "2900 757\n",
      "2901 312\n",
      "2902 544\n",
      "2903 1789\n",
      "2904 834\n",
      "2905 7327\n",
      "2906 3550\n",
      "2907 568\n",
      "2908 1053\n",
      "2909 641\n",
      "2910 1458\n",
      "2911 6141\n",
      "2912 115\n",
      "2913 113\n",
      "2914 325\n",
      "2915 359\n",
      "2916 2967\n",
      "2917 224\n",
      "2918 192\n",
      "2919 870\n",
      "2920 320\n",
      "2921 694\n",
      "2922 93\n",
      "2923 12135\n",
      "2924 13287\n",
      "2925 3069\n",
      "2926 7723\n",
      "2927 7510\n",
      "2928 148\n",
      "2929 44\n",
      "2930 875\n",
      "2931 106\n",
      "2932 905\n",
      "2933 722\n",
      "2934 113\n",
      "2935 628\n",
      "2936 621\n",
      "2937 112\n",
      "2938 3335\n",
      "2939 3462\n",
      "2940 3856\n",
      "2941 2696\n",
      "2942 149\n",
      "2943 59\n",
      "2944 283\n",
      "2945 45\n",
      "2946 1223\n",
      "2947 392\n",
      "2948 285\n",
      "2949 410\n",
      "2950 1774\n",
      "2951 801\n",
      "2952 227\n",
      "2953 2909\n",
      "2954 608\n",
      "2955 766\n",
      "2956 929\n",
      "2957 3482\n",
      "2958 284\n",
      "2959 1399\n",
      "2960 2381\n",
      "2961 172\n",
      "2962 1627\n",
      "2963 429\n",
      "2964 94\n",
      "2965 3137\n",
      "2966 2863\n",
      "2967 890\n",
      "2968 350\n",
      "2969 2979\n",
      "2970 4201\n",
      "2971 4518\n",
      "2972 55\n",
      "2973 1115\n",
      "2974 244\n",
      "2975 989\n",
      "2976 672\n",
      "2977 203\n",
      "2978 566\n",
      "2979 107\n",
      "2980 236\n",
      "2981 1587\n",
      "2982 1044\n",
      "2983 563\n",
      "2984 535\n",
      "2985 67\n",
      "2986 114\n",
      "2987 2085\n",
      "2988 881\n",
      "2989 1685\n",
      "2990 113\n",
      "2991 56\n",
      "2992 1461\n",
      "2993 306\n",
      "2994 730\n",
      "2995 5610\n",
      "2996 375\n",
      "2997 1611\n",
      "2998 195\n",
      "2999 241\n",
      "3000 1584\n",
      "3001 43\n",
      "3002 497\n",
      "3003 1122\n",
      "3004 1216\n",
      "3005 429\n",
      "3006 652\n",
      "3007 537\n",
      "3008 1608\n",
      "3009 551\n",
      "3010 916\n",
      "3011 94\n",
      "3012 1349\n",
      "3013 360\n",
      "3014 839\n",
      "3015 215\n",
      "3016 1086\n",
      "3017 1410\n",
      "3018 604\n",
      "3019 677\n",
      "3020 3056\n",
      "3021 513\n",
      "3022 5347\n",
      "3023 460\n",
      "3024 1112\n",
      "3025 293\n",
      "3026 798\n",
      "3027 4679\n",
      "3028 233\n",
      "3029 290\n",
      "3030 20458\n",
      "3031 1413\n",
      "3032 56\n",
      "3033 912\n",
      "3034 1262\n",
      "3035 1897\n",
      "3036 180\n",
      "3037 809\n",
      "3038 633\n",
      "3039 1455\n",
      "3040 1987\n",
      "3041 318\n",
      "3042 1129\n",
      "3043 413\n",
      "3044 2079\n",
      "3045 1041\n",
      "3046 301\n",
      "3047 1447\n",
      "3048 186\n",
      "3049 2430\n",
      "3050 140\n",
      "3051 189\n",
      "3052 538\n",
      "3053 137\n",
      "3054 1103\n",
      "3055 916\n",
      "3056 1734\n",
      "3057 701\n",
      "3058 276\n",
      "3059 9848\n",
      "3060 1081\n",
      "3061 117\n",
      "3062 99\n",
      "3063 269\n",
      "3064 103\n",
      "3065 1279\n",
      "3066 155\n",
      "3067 1557\n",
      "3068 1378\n",
      "3069 827\n",
      "3070 314\n",
      "3071 932\n",
      "3072 91\n",
      "3073 101\n",
      "3074 873\n",
      "3075 234\n",
      "3076 93\n",
      "3077 830\n",
      "3078 172\n",
      "3079 1368\n",
      "3080 738\n",
      "3081 434\n",
      "3082 264\n",
      "3083 345\n",
      "3084 2883\n",
      "3085 1064\n",
      "3086 222\n",
      "3087 13816\n",
      "3088 47\n",
      "3089 685\n",
      "3090 316\n",
      "3091 846\n",
      "3092 250\n",
      "3093 102\n",
      "3094 369\n",
      "3095 4346\n",
      "3096 863\n",
      "3097 663\n",
      "3098 170\n",
      "3099 393\n",
      "3100 141\n",
      "3101 433\n",
      "3102 189\n",
      "3103 1464\n",
      "3104 206\n",
      "3105 2116\n",
      "3106 9992\n",
      "3107 418\n",
      "3108 390\n",
      "3109 1586\n",
      "3110 2265\n",
      "3111 221\n",
      "3112 665\n",
      "3113 29\n",
      "3114 604\n",
      "3115 670\n",
      "3116 866\n",
      "3117 307\n",
      "3118 469\n",
      "3119 1018\n",
      "3120 4057\n",
      "3121 142\n",
      "3122 1034\n",
      "3123 177\n",
      "3124 134\n",
      "3125 263\n",
      "3126 103\n",
      "3127 337\n",
      "3128 301\n",
      "3129 257\n",
      "3130 181\n",
      "3131 441\n",
      "3132 360\n",
      "3133 312\n",
      "3134 140\n",
      "3135 163\n",
      "3136 55\n",
      "3137 1513\n",
      "3138 2454\n",
      "3139 1427\n",
      "3140 442\n",
      "3141 161\n",
      "3142 924\n",
      "3143 20003\n",
      "3144 262\n",
      "3145 3120\n",
      "3146 212\n",
      "3147 749\n",
      "3148 116\n",
      "3149 53\n",
      "3150 80\n",
      "3151 205\n",
      "3152 391\n",
      "3153 342\n",
      "3154 759\n",
      "3155 1125\n",
      "3156 1161\n",
      "3157 1386\n",
      "3158 1066\n",
      "3159 485\n",
      "3160 873\n",
      "3161 836\n",
      "3162 1719\n",
      "3163 2994\n",
      "3164 1122\n",
      "3165 128\n",
      "3166 43\n",
      "3167 1090\n",
      "3168 51\n",
      "3169 234\n",
      "3170 1854\n",
      "3171 3637\n",
      "3172 435\n",
      "3173 1842\n",
      "3174 141\n",
      "3175 223\n",
      "3176 217\n",
      "3177 367\n",
      "3178 972\n",
      "3179 1083\n",
      "3180 4238\n",
      "3181 1469\n",
      "3182 1196\n",
      "3183 612\n",
      "3184 2022\n",
      "3185 195\n",
      "3186 684\n",
      "3187 149\n",
      "3188 771\n",
      "3189 995\n",
      "3190 1329\n",
      "3191 3305\n",
      "3192 3355\n",
      "3193 1843\n",
      "3194 2935\n",
      "3195 2739\n",
      "3196 241\n",
      "3197 302\n",
      "3198 3630\n",
      "3199 385\n",
      "3200 5023\n",
      "3201 4886\n",
      "3202 137\n",
      "3203 57\n",
      "3204 831\n",
      "3205 2612\n",
      "3206 2703\n",
      "3207 966\n",
      "3208 12738\n",
      "3209 700\n",
      "3210 1693\n",
      "3211 1618\n",
      "3212 227\n",
      "3213 109\n",
      "3214 191\n",
      "3215 542\n",
      "3216 580\n",
      "3217 764\n",
      "3218 689\n",
      "3219 1266\n",
      "3220 502\n",
      "3221 1004\n",
      "3222 2369\n",
      "3223 2184\n",
      "3224 1905\n",
      "3225 1472\n",
      "3226 2365\n",
      "3227 346\n",
      "3228 131\n",
      "3229 121\n",
      "3230 209\n",
      "3231 705\n",
      "3232 805\n",
      "3233 2662\n",
      "3234 599\n",
      "3235 651\n",
      "3236 804\n",
      "3237 187\n",
      "3238 779\n",
      "3239 357\n",
      "3240 205\n",
      "3241 1311\n",
      "3242 1156\n",
      "3243 215\n",
      "3244 552\n",
      "3245 229\n",
      "3246 48\n",
      "3247 113\n",
      "3248 521\n",
      "3249 20613\n",
      "3250 834\n",
      "3251 1755\n",
      "3252 267\n",
      "3253 17238\n",
      "3254 1076\n",
      "3255 120\n",
      "3256 646\n",
      "3257 1340\n",
      "3258 140\n",
      "3259 3599\n",
      "3260 501\n",
      "3261 35\n",
      "3262 796\n",
      "3263 6098\n",
      "3264 7826\n",
      "3265 2746\n",
      "3266 2350\n",
      "3267 854\n",
      "3268 225\n",
      "3269 10114\n",
      "3270 651\n",
      "3271 89\n",
      "3272 158\n",
      "3273 693\n",
      "3274 733\n",
      "3275 320\n",
      "3276 5\n",
      "3277 2710\n",
      "3278 488\n",
      "3279 954\n",
      "3280 66\n",
      "3281 450\n",
      "3282 4407\n",
      "3283 672\n",
      "3284 57\n",
      "3285 3102\n",
      "3286 333\n",
      "3287 1512\n",
      "3288 3092\n",
      "3289 4175\n",
      "3290 3512\n",
      "3291 665\n",
      "3292 2075\n",
      "3293 458\n",
      "3294 113\n",
      "3295 5191\n",
      "3296 93\n",
      "3297 16408\n",
      "3298 623\n",
      "3299 248\n",
      "3300 773\n",
      "3301 945\n",
      "3302 1457\n",
      "3303 1307\n",
      "3304 479\n",
      "3305 1011\n",
      "3306 78\n",
      "3307 240\n",
      "3308 131\n",
      "3309 447\n",
      "3310 7995\n",
      "3311 127\n",
      "3312 49\n",
      "3313 203\n",
      "3314 204\n",
      "3315 1183\n",
      "3316 289\n",
      "3317 2389\n",
      "3318 228\n",
      "3319 307\n",
      "3320 2298\n",
      "3321 443\n",
      "3322 761\n",
      "3323 65\n",
      "3324 985\n",
      "3325 45\n",
      "3326 1228\n",
      "3327 186\n",
      "3328 1303\n",
      "3329 108\n",
      "3330 803\n",
      "3331 540\n",
      "3332 1230\n",
      "3333 82\n",
      "3334 115\n",
      "3335 1317\n",
      "3336 478\n",
      "3337 287\n",
      "3338 1392\n",
      "3339 2326\n",
      "3340 2176\n",
      "3341 533\n",
      "3342 1074\n",
      "3343 1826\n",
      "3344 1013\n",
      "3345 864\n",
      "3346 783\n",
      "3347 17185\n",
      "3348 102\n",
      "3349 466\n",
      "3350 50\n",
      "3351 519\n",
      "3352 650\n",
      "3353 51\n",
      "3354 674\n",
      "3355 17722\n",
      "3356 441\n",
      "3357 191\n",
      "3358 2315\n",
      "3359 1377\n",
      "3360 252\n",
      "3361 2863\n",
      "3362 935\n",
      "3363 80\n",
      "3364 23696\n",
      "3365 1067\n",
      "3366 202\n",
      "3367 196\n",
      "3368 304\n",
      "3369 214\n",
      "3370 1873\n",
      "3371 203\n",
      "3372 153\n",
      "3373 82\n",
      "3374 5378\n",
      "3375 46\n",
      "3376 3234\n",
      "3377 533\n",
      "3378 1054\n",
      "3379 1050\n",
      "3380 348\n",
      "3381 3125\n",
      "3382 5119\n",
      "3383 3623\n",
      "3384 242\n",
      "3385 9953\n",
      "3386 5220\n",
      "3387 121\n",
      "3388 215\n",
      "3389 462\n",
      "3390 83\n",
      "3391 299\n",
      "3392 2091\n",
      "3393 2353\n",
      "3394 153\n",
      "3395 1188\n",
      "3396 169\n",
      "3397 86\n",
      "3398 3897\n",
      "3399 674\n",
      "3400 945\n",
      "3401 91\n",
      "3402 354\n",
      "3403 182\n",
      "3404 47\n",
      "3405 253\n",
      "3406 220\n",
      "3407 92\n",
      "3408 172\n",
      "3409 50\n",
      "3410 117\n",
      "3411 140\n",
      "3412 961\n",
      "3413 358\n",
      "3414 246\n",
      "3415 771\n",
      "3416 3084\n",
      "3417 66\n",
      "3418 19\n",
      "3419 432\n",
      "3420 365\n",
      "3421 1018\n",
      "3422 50\n",
      "3423 267\n",
      "3424 782\n",
      "3425 34\n",
      "3426 684\n",
      "3427 260\n",
      "3428 195\n",
      "3429 271\n",
      "3430 255\n",
      "3431 923\n",
      "3432 222\n",
      "3433 962\n",
      "3434 352\n",
      "3435 2143\n",
      "3436 80\n",
      "3437 208\n",
      "3438 703\n",
      "3439 825\n",
      "3440 865\n",
      "3441 336\n",
      "3442 266\n",
      "3443 920\n",
      "3444 433\n",
      "3445 34\n",
      "3446 1890\n",
      "3447 8650\n",
      "3448 83\n",
      "3449 509\n",
      "3450 58\n",
      "3451 2900\n",
      "3452 1022\n",
      "3453 2246\n",
      "3454 2265\n",
      "3455 268\n",
      "3456 310\n",
      "3457 111\n",
      "3458 153\n",
      "3459 2994\n",
      "3460 98\n",
      "3461 191\n",
      "3462 481\n",
      "3463 47\n",
      "3464 52\n",
      "3465 491\n",
      "3466 89\n",
      "3467 182\n",
      "3468 178\n",
      "3469 189\n",
      "3470 386\n",
      "3471 73\n",
      "3472 3150\n",
      "3473 61\n",
      "3474 98\n",
      "3475 3048\n",
      "3476 3705\n",
      "3477 1215\n",
      "3478 765\n",
      "3479 360\n",
      "3480 98\n",
      "3481 74\n",
      "3482 120\n",
      "3483 52\n",
      "3484 222\n",
      "3485 444\n",
      "3486 97\n",
      "3487 147\n",
      "3488 7433\n",
      "3489 1060\n",
      "3490 4404\n",
      "3491 254\n",
      "3492 222\n",
      "3493 4296\n",
      "3494 209\n",
      "3495 224\n",
      "3496 499\n",
      "3497 278\n",
      "3498 170\n",
      "3499 193\n",
      "3500 99\n",
      "3501 112\n",
      "3502 11647\n",
      "3503 17918\n",
      "3504 83\n",
      "3505 1614\n",
      "3506 114\n",
      "3507 753\n",
      "3508 49\n",
      "3509 3717\n",
      "3510 120\n",
      "3511 2492\n",
      "3512 9418\n",
      "3513 4630\n",
      "3514 2345\n",
      "3515 4718\n",
      "3516 121\n",
      "3517 6641\n",
      "3518 96\n",
      "3519 133\n",
      "3520 129\n",
      "3521 131\n",
      "3522 923\n",
      "3523 1080\n",
      "3524 101\n",
      "3525 8867\n",
      "3526 63\n",
      "3527 1082\n",
      "3528 126\n",
      "3529 75\n",
      "3530 108\n",
      "3531 1072\n",
      "3532 1154\n",
      "3533 42\n",
      "3534 1194\n",
      "3535 34\n",
      "3536 2694\n",
      "3537 1322\n",
      "3538 75\n",
      "3539 90\n",
      "3540 76\n",
      "3541 696\n",
      "3542 170\n",
      "3543 1471\n",
      "3544 47\n",
      "3545 86\n",
      "3546 434\n",
      "3547 101\n",
      "3548 658\n",
      "3549 631\n",
      "3550 106\n",
      "3551 175\n",
      "3552 230\n",
      "3553 242\n",
      "3554 270\n",
      "3555 48\n",
      "3556 118\n",
      "3557 217\n",
      "3558 118\n",
      "3559 109\n",
      "3560 216\n",
      "3561 457\n",
      "3562 345\n",
      "3563 118\n",
      "3564 56\n",
      "3565 63\n",
      "3566 585\n",
      "3567 124\n",
      "3568 2337\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "3569 268\n",
      "3570 1364\n",
      "3571 237\n",
      "3572 521\n",
      "3573 765\n",
      "3574 194\n",
      "3575 50\n",
      "3576 194\n",
      "3577 151\n",
      "3578 3991\n",
      "3579 196\n",
      "3580 2311\n",
      "3581 430\n",
      "3582 1493\n",
      "3583 1401\n",
      "3584 1607\n",
      "3585 12783\n",
      "3586 340\n",
      "3587 44\n",
      "3588 443\n",
      "3589 904\n",
      "3590 1530\n",
      "3591 782\n",
      "3592 1634\n",
      "3593 50\n",
      "3594 407\n",
      "3595 2776\n",
      "3596 2503\n",
      "3597 1391\n",
      "3598 68\n",
      "3599 335\n",
      "3600 558\n",
      "3601 382\n",
      "3602 181\n",
      "3603 176\n",
      "3604 353\n",
      "3605 2440\n",
      "3606 1259\n",
      "3607 893\n",
      "3608 1528\n",
      "3609 3186\n",
      "3610 1106\n",
      "3611 520\n",
      "3612 206\n",
      "3613 2635\n",
      "3614 597\n",
      "3615 8066\n",
      "3616 1004\n",
      "3617 1369\n",
      "3618 1141\n",
      "3619 2148\n",
      "3620 2854\n",
      "3621 757\n",
      "3622 3124\n",
      "3623 580\n",
      "3624 789\n",
      "3625 6113\n",
      "3626 612\n",
      "3627 1536\n",
      "3628 1553\n",
      "3629 2532\n",
      "3630 2229\n",
      "3631 397\n",
      "3632 2289\n",
      "3633 2296\n",
      "3634 852\n",
      "3635 4151\n",
      "3636 225\n",
      "3637 21046\n",
      "3638 6\n",
      "3639 802\n",
      "3640 358\n",
      "3641 406\n",
      "3642 498\n",
      "3643 729\n",
      "3644 2306\n",
      "3645 916\n",
      "3646 47\n",
      "3647 817\n",
      "3648 902\n",
      "3649 8061\n",
      "3650 1595\n",
      "3651 164\n",
      "3652 2403\n",
      "3653 44\n",
      "3654 13499\n",
      "3655 8516\n",
      "3656 2470\n",
      "3657 692\n",
      "3658 690\n",
      "3659 4618\n",
      "3660 6136\n",
      "3661 943\n",
      "3662 9163\n",
      "3663 5873\n",
      "3664 11767\n",
      "3665 1629\n",
      "3666 3855\n",
      "3667 1027\n",
      "3668 3616\n",
      "3669 3214\n",
      "3670 13786\n",
      "3671 2537\n",
      "3672 9750\n",
      "3673 1383\n",
      "3674 5705\n",
      "3675 443\n",
      "3676 2450\n",
      "3677 935\n",
      "3678 0\n",
      "3679 881\n",
      "3680 517\n",
      "3681 6978\n",
      "3682 10844\n",
      "3683 1082\n",
      "3684 1690\n",
      "3685 5670\n",
      "3686 2713\n",
      "3687 6082\n",
      "3688 5541\n",
      "3689 908\n",
      "3690 3324\n",
      "3691 1177\n",
      "3692 17387\n",
      "3693 1652\n",
      "3694 8779\n",
      "3695 1030\n",
      "3696 713\n",
      "3697 5692\n",
      "3698 688\n",
      "3699 1428\n",
      "3700 6491\n",
      "3701 670\n",
      "3702 4882\n",
      "3703 3851\n",
      "3704 5165\n",
      "3705 1993\n",
      "3706 425\n",
      "3707 5649\n",
      "3708 12645\n",
      "3709 7196\n",
      "3710 4131\n",
      "3711 868\n",
      "3712 22643\n",
      "3713 2684\n",
      "3714 3234\n",
      "3715 7806\n",
      "3716 23659\n",
      "3717 908\n",
      "3718 1850\n",
      "3719 21570\n",
      "3720 6442\n",
      "3721 304\n",
      "3722 1104\n",
      "3723 1145\n",
      "3724 8867\n",
      "3725 4635\n",
      "3726 3109\n",
      "3727 2355\n",
      "3728 9806\n",
      "3729 4000\n",
      "3730 3584\n",
      "3731 1484\n",
      "3732 6496\n",
      "3733 4596\n",
      "3734 2264\n",
      "3735 1098\n",
      "3736 5345\n",
      "3737 3609\n",
      "3738 14859\n",
      "3739 966\n",
      "3740 2398\n",
      "3741 5483\n",
      "3742 12428\n",
      "3743 3433\n",
      "3744 348\n",
      "3745 4666\n",
      "3746 184\n",
      "3747 940\n",
      "3748 858\n",
      "3749 1720\n",
      "3750 409\n",
      "3751 501\n",
      "3752 5996\n",
      "3753 6167\n",
      "3754 3119\n",
      "3755 478\n",
      "3756 4311\n",
      "3757 139\n",
      "3758 1447\n",
      "3759 4824\n",
      "3760 256\n",
      "3761 10413\n",
      "3762 4061\n",
      "3763 1002\n",
      "3764 13784\n",
      "3765 13636\n",
      "3766 1064\n",
      "3767 6925\n",
      "3768 16142\n",
      "3769 4342\n",
      "3770 853\n",
      "3771 947\n",
      "3772 7348\n",
      "3773 1574\n",
      "3774 1020\n",
      "3775 7547\n",
      "3776 2232\n",
      "3777 5057\n",
      "3778 6764\n",
      "3779 28756\n",
      "3780 12146\n",
      "3781 24953\n",
      "3782 883\n",
      "3783 2790\n",
      "3784 3296\n",
      "3785 4369\n",
      "3786 23967\n",
      "3787 8113\n",
      "3788 6315\n",
      "3789 8466\n",
      "3790 16070\n",
      "3791 3185\n",
      "3792 8297\n",
      "3793 527\n",
      "3794 9309\n",
      "3795 1190\n",
      "3796 19780\n",
      "3797 734\n",
      "3798 10752\n",
      "3799 1148\n",
      "3800 932\n",
      "3801 126\n",
      "3802 17346\n",
      "3803 7140\n",
      "3804 13394\n",
      "3805 15684\n",
      "3806 257\n",
      "3807 855\n",
      "3808 443\n",
      "3809 1119\n",
      "3810 718\n",
      "3811 12710\n",
      "3812 2393\n",
      "3813 348\n",
      "3814 9243\n",
      "3815 6450\n",
      "3816 681\n",
      "3817 8044\n",
      "3818 638\n",
      "3819 4086\n",
      "3820 3734\n",
      "3821 8824\n",
      "3822 1356\n",
      "3823 7802\n",
      "3824 2884\n",
      "3825 8321\n",
      "3826 23547\n",
      "3827 22879\n",
      "3828 32121\n",
      "3829 11\n",
      "3830 324\n",
      "3831 405\n",
      "3832 3733\n",
      "3833 2187\n",
      "3834 2260\n",
      "3835 163\n",
      "3836 6428\n",
      "3837 643\n",
      "3838 1006\n",
      "3839 569\n",
      "3840 834\n",
      "3841 1703\n",
      "3842 924\n",
      "3843 1602\n",
      "3844 343\n",
      "3845 217\n",
      "3846 3217\n",
      "3847 441\n",
      "3848 3431\n",
      "3849 282\n",
      "3850 1099\n",
      "3851 4482\n",
      "3852 3869\n",
      "3853 646\n",
      "3854 1841\n",
      "3855 1642\n",
      "3856 1251\n",
      "3857 312\n",
      "3858 903\n",
      "3859 918\n",
      "3860 1487\n",
      "3861 5608\n",
      "3862 1867\n",
      "3863 6593\n",
      "3864 22532\n",
      "3865 2470\n",
      "3866 4662\n",
      "3867 316\n",
      "3868 14789\n",
      "3869 3715\n",
      "3870 1864\n",
      "3871 613\n",
      "3872 5686\n",
      "3873 12179\n",
      "3874 5039\n",
      "3875 1246\n",
      "3876 6967\n",
      "3877 3101\n",
      "3878 7490\n",
      "3879 1003\n",
      "3880 1448\n",
      "3881 1878\n",
      "3882 1849\n",
      "3883 23794\n",
      "3884 1527\n",
      "3885 436\n",
      "3886 9550\n",
      "3887 3389\n",
      "3888 3854\n",
      "3889 2077\n",
      "3890 845\n",
      "3891 5722\n",
      "3892 2583\n",
      "3893 481\n",
      "3894 1508\n",
      "3895 336\n",
      "3896 736\n",
      "3897 110\n",
      "3898 22731\n",
      "3899 1323\n",
      "3900 2035\n",
      "3901 681\n",
      "3902 2754\n",
      "3903 1072\n",
      "3904 21959\n",
      "3905 2619\n",
      "3906 413\n",
      "3907 5176\n",
      "3908 7459\n",
      "3909 1566\n",
      "3910 3114\n",
      "3911 5752\n",
      "3912 2705\n",
      "3913 2710\n",
      "3914 1527\n",
      "3915 9664\n",
      "3916 3382\n",
      "3917 1613\n",
      "3918 1803\n",
      "3919 473\n",
      "3920 3209\n",
      "3921 290\n",
      "3922 3387\n",
      "3923 4611\n",
      "3924 1639\n",
      "3925 3012\n",
      "3926 13132\n",
      "3927 1557\n",
      "3928 4040\n",
      "3929 887\n",
      "3930 904\n",
      "3931 856\n",
      "3932 15918\n",
      "3933 5351\n",
      "3934 1064\n",
      "3935 3403\n",
      "3936 3641\n",
      "3937 439\n",
      "3938 14596\n",
      "3939 230\n",
      "3940 1220\n",
      "3941 5126\n",
      "3942 1159\n",
      "3943 205\n",
      "3944 2065\n",
      "3945 163\n",
      "3946 562\n",
      "3947 1665\n",
      "3948 9105\n",
      "3949 179\n",
      "3950 497\n",
      "3951 319\n",
      "3952 1733\n",
      "3953 1322\n",
      "3954 50\n",
      "3955 3164\n",
      "3956 422\n",
      "3957 3899\n",
      "3958 424\n",
      "3959 465\n",
      "3960 1063\n",
      "3961 1125\n",
      "3962 237\n",
      "3963 446\n",
      "3964 456\n",
      "3965 680\n",
      "3966 510\n",
      "3967 1456\n",
      "3968 181\n",
      "3969 9186\n",
      "3970 5266\n",
      "3971 17191\n",
      "3972 1520\n",
      "3973 1828\n",
      "3974 8550\n",
      "3975 10008\n",
      "3976 377\n",
      "3977 815\n",
      "3978 11570\n",
      "3979 392\n",
      "3980 9934\n",
      "3981 1656\n",
      "3982 4507\n",
      "3983 7198\n",
      "3984 2636\n",
      "3985 23637\n",
      "3986 22772\n",
      "3987 2551\n",
      "3988 10297\n",
      "3989 43442\n",
      "3990 1387\n",
      "3991 2296\n",
      "3992 3531\n",
      "3993 3437\n",
      "3994 23807\n",
      "3995 6028\n",
      "3996 2780\n",
      "3997 6043\n",
      "3998 2770\n",
      "3999 1214\n",
      "4000 365\n",
      "4001 0\n",
      "4002 61\n",
      "4003 492\n",
      "4004 489\n",
      "4005 1548\n",
      "4006 533\n",
      "4007 407\n",
      "4008 1241\n",
      "4009 1659\n",
      "4010 4074\n",
      "4011 1270\n",
      "4012 1548\n",
      "4013 538\n",
      "4014 4696\n",
      "4015 1159\n",
      "4016 1778\n",
      "4017 960\n",
      "4018 505\n",
      "4019 5118\n",
      "4020 454\n",
      "4021 56\n",
      "4022 665\n",
      "4023 380\n",
      "4024 66\n",
      "4025 2178\n",
      "4026 486\n",
      "4027 372\n",
      "4028 447\n",
      "4029 2264\n",
      "4030 1489\n",
      "4031 4525\n",
      "4032 1663\n",
      "4033 1027\n",
      "4034 10057\n",
      "4035 3363\n",
      "4036 2828\n",
      "4037 7952\n",
      "4038 536\n",
      "4039 3382\n",
      "4040 910\n",
      "4041 7429\n",
      "4042 1208\n",
      "4043 3020\n",
      "4044 4139\n",
      "4045 5946\n",
      "4046 4679\n",
      "4047 11383\n",
      "4048 5282\n",
      "4049 2257\n",
      "4050 25203\n",
      "4051 1896\n",
      "4052 768\n",
      "4053 2607\n",
      "4054 2081\n",
      "4055 502\n",
      "4056 5930\n",
      "4057 7582\n",
      "4058 15164\n",
      "4059 5248\n",
      "4060 793\n",
      "4061 13586\n",
      "4062 3858\n",
      "4063 2061\n",
      "4064 4332\n",
      "4065 3089\n",
      "4066 3747\n",
      "4067 12803\n",
      "4068 548\n",
      "4069 3473\n",
      "4070 8883\n",
      "4071 10389\n",
      "4072 459\n",
      "4073 3560\n",
      "4074 16951\n",
      "4075 5323\n",
      "4076 4675\n",
      "4077 7093\n",
      "4078 6956\n",
      "4079 8407\n",
      "4080 398\n",
      "4081 1006\n",
      "4082 11442\n",
      "4083 2187\n",
      "4084 2102\n",
      "4085 5632\n",
      "4086 2633\n",
      "4087 1588\n",
      "4088 571\n",
      "4089 1137\n",
      "4090 1879\n",
      "4091 1817\n",
      "4092 6670\n",
      "4093 506\n",
      "4094 1752\n",
      "4095 1113\n",
      "4096 1826\n",
      "4097 627\n",
      "4098 816\n",
      "4099 5701\n",
      "4100 1044\n",
      "4101 1268\n",
      "4102 5189\n",
      "4103 2654\n",
      "4104 391\n",
      "4105 1553\n",
      "4106 1214\n",
      "4107 4816\n",
      "4108 484\n",
      "4109 5862\n",
      "4110 5980\n",
      "4111 5244\n",
      "4112 22817\n",
      "4113 5198\n",
      "4114 4781\n",
      "4115 6184\n",
      "4116 6771\n",
      "4117 518\n",
      "4118 1518\n",
      "4119 14077\n",
      "4120 2442\n",
      "4121 3588\n",
      "4122 3134\n",
      "4123 5626\n",
      "4124 6751\n",
      "4125 12339\n",
      "4126 5720\n",
      "4127 197\n",
      "4128 2406\n",
      "4129 1056\n",
      "4130 1617\n",
      "4131 308\n",
      "4132 1296\n",
      "4133 1328\n",
      "4134 485\n",
      "4135 551\n",
      "4136 1196\n",
      "4137 426\n",
      "4138 3385\n",
      "4139 416\n",
      "4140 1186\n",
      "4141 2388\n",
      "4142 1717\n",
      "4143 182\n",
      "4144 2834\n",
      "4145 23328\n",
      "4146 5704\n",
      "4147 1022\n",
      "4148 1928\n",
      "4149 22311\n",
      "4150 2548\n",
      "4151 1248\n",
      "4152 1092\n",
      "4153 25333\n",
      "4154 4703\n",
      "4155 1230\n",
      "4156 1527\n",
      "4157 627\n",
      "4158 5469\n",
      "4159 1417\n",
      "4160 855\n",
      "4161 3723\n",
      "4162 6912\n",
      "4163 2816\n",
      "4164 2952\n",
      "4165 1997\n",
      "4166 874\n",
      "4167 525\n",
      "4168 4652\n",
      "4169 8085\n",
      "4170 1243\n",
      "4171 2102\n",
      "4172 3474\n",
      "4173 6224\n",
      "4174 7186\n",
      "4175 3811\n",
      "4176 9331\n",
      "4177 4301\n",
      "4178 23542\n",
      "4179 3842\n",
      "4180 282\n",
      "4181 5195\n",
      "4182 2428\n",
      "4183 8001\n",
      "4184 6324\n",
      "4185 6888\n",
      "4186 3068\n",
      "4187 2942\n",
      "4188 903\n",
      "4189 97\n",
      "4190 589\n",
      "4191 2537\n",
      "4192 439\n",
      "4193 2374\n",
      "4194 1053\n",
      "4195 352\n",
      "4196 257\n",
      "4197 1128\n",
      "4198 1040\n",
      "4199 11312\n",
      "4200 1372\n",
      "4201 1642\n",
      "4202 130\n",
      "4203 96\n",
      "4204 2338\n",
      "4205 239\n",
      "4206 768\n",
      "4207 1422\n",
      "4208 4670\n",
      "4209 1439\n",
      "4210 829\n",
      "4211 1599\n",
      "4212 8493\n",
      "4213 3850\n",
      "4214 9098\n",
      "4215 22737\n",
      "4216 201\n",
      "4217 1319\n",
      "4218 1932\n",
      "4219 3073\n",
      "4220 2778\n",
      "4221 1682\n",
      "4222 834\n",
      "4223 6528\n",
      "4224 5096\n",
      "4225 3735\n",
      "4226 14175\n",
      "4227 6103\n",
      "4228 6877\n",
      "4229 1355\n",
      "4230 1082\n",
      "4231 751\n",
      "4232 4070\n",
      "4233 6181\n",
      "4234 1045\n",
      "4235 10404\n",
      "4236 6022\n",
      "4237 14165\n",
      "4238 26278\n",
      "4239 2903\n",
      "4240 400\n",
      "4241 8231\n",
      "4242 1669\n",
      "4243 2634\n",
      "4244 3116\n",
      "4245 13872\n",
      "4246 1744\n",
      "4247 3725\n",
      "4248 1379\n",
      "4249 2336\n",
      "4250 1943\n",
      "4251 6017\n",
      "4252 1334\n",
      "4253 2138\n",
      "4254 1375\n",
      "4255 11\n",
      "4256 2199\n",
      "4257 1087\n",
      "4258 202\n",
      "4259 829\n",
      "4260 1063\n",
      "4261 387\n",
      "4262 156\n",
      "4263 489\n",
      "4264 2326\n",
      "4265 331\n",
      "4266 82\n",
      "4267 2780\n",
      "4268 1989\n",
      "4269 1742\n",
      "4270 11111\n",
      "4271 413\n",
      "4272 4082\n",
      "4273 1968\n",
      "4274 3704\n",
      "4275 732\n",
      "4276 1257\n",
      "4277 11512\n",
      "4278 5096\n",
      "4279 2981\n",
      "4280 3230\n",
      "4281 3144\n",
      "4282 1045\n",
      "4283 832\n",
      "4284 24102\n",
      "4285 9815\n",
      "4286 12398\n",
      "4287 7402\n",
      "4288 2240\n",
      "4289 3798\n",
      "4290 488\n",
      "4291 7601\n",
      "4292 2021\n",
      "4293 3552\n",
      "4294 13829\n",
      "4295 597\n",
      "4296 2238\n",
      "4297 12\n",
      "4298 387\n",
      "4299 1351\n",
      "4300 47\n",
      "4301 919\n",
      "4302 2433\n",
      "4303 2251\n",
      "4304 720\n",
      "4305 2280\n",
      "4306 893\n",
      "4307 260\n",
      "4308 481\n",
      "4309 399\n",
      "4310 1102\n",
      "4311 20570\n",
      "4312 20707\n",
      "4313 4482\n",
      "4314 5411\n",
      "4315 1825\n",
      "4316 1593\n",
      "4317 1128\n",
      "4318 251\n",
      "4319 25880\n",
      "4320 1724\n",
      "4321 3461\n",
      "4322 2144\n",
      "4323 726\n",
      "4324 6596\n",
      "4325 658\n",
      "4326 4853\n",
      "4327 2535\n",
      "4328 532\n",
      "4329 6042\n",
      "4330 2844\n",
      "4331 11408\n",
      "4332 2257\n",
      "4333 5445\n",
      "4334 316\n",
      "4335 4626\n",
      "4336 6104\n",
      "4337 1667\n",
      "4338 1645\n",
      "4339 4424\n",
      "4340 2040\n",
      "4341 6881\n",
      "4342 2571\n",
      "4343 1893\n",
      "4344 4183\n",
      "4345 3865\n",
      "4346 822\n",
      "4347 1692\n",
      "4348 20093\n",
      "4349 607\n",
      "4350 15742\n",
      "4351 6329\n",
      "4352 322\n",
      "4353 2315\n",
      "4354 50\n",
      "4355 710\n",
      "4356 11\n",
      "4357 28\n",
      "4358 65\n",
      "4359 5194\n",
      "4360 285\n",
      "4361 247\n",
      "4362 1195\n",
      "4363 1444\n",
      "4364 574\n",
      "4365 1932\n",
      "4366 4503\n",
      "4367 2405\n",
      "4368 1060\n",
      "4369 3405\n",
      "4370 896\n",
      "4371 7979\n",
      "4372 1298\n",
      "4373 6413\n",
      "4374 3531\n",
      "4375 2450\n",
      "4376 6192\n",
      "4377 8829\n",
      "4378 9546\n",
      "4379 3044\n",
      "4380 1695\n",
      "4381 18305\n",
      "4382 8135\n",
      "4383 4809\n",
      "4384 1169\n",
      "4385 2986\n",
      "4386 15350\n",
      "4387 1011\n",
      "4388 522\n",
      "4389 434\n",
      "4390 1733\n",
      "4391 1300\n",
      "4392 16974\n",
      "4393 345\n",
      "4394 3480\n",
      "4395 1504\n",
      "4396 1995\n",
      "4397 480\n",
      "4398 1814\n",
      "4399 4756\n",
      "4400 4296\n",
      "4401 628\n",
      "4402 9476\n",
      "4403 8353\n",
      "4404 7094\n",
      "4405 20001\n",
      "4406 6940\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "4407 3161\n",
      "4408 2436\n",
      "4409 3212\n",
      "4410 15097\n",
      "4411 12017\n",
      "4412 2624\n",
      "4413 3875\n",
      "4414 2484\n",
      "4415 1702\n",
      "4416 300\n",
      "4417 8339\n",
      "4418 1493\n",
      "4419 2852\n",
      "4420 393\n",
      "4421 276\n",
      "4422 116\n",
      "4423 1445\n",
      "4424 306\n",
      "4425 2712\n",
      "4426 522\n",
      "4427 611\n",
      "4428 1876\n",
      "4429 1980\n",
      "4430 1631\n",
      "4431 1107\n",
      "4432 702\n",
      "4433 1651\n",
      "4434 5039\n",
      "4435 3752\n",
      "4436 24479\n",
      "4437 15228\n",
      "4438 5642\n",
      "4439 6690\n",
      "4440 3846\n",
      "4441 686\n",
      "4442 2578\n",
      "4443 2549\n",
      "4444 22823\n",
      "4445 5002\n",
      "4446 11797\n",
      "4447 2259\n",
      "4448 1107\n",
      "4449 777\n",
      "4450 9470\n",
      "4451 17201\n",
      "4452 23246\n",
      "4453 11330\n",
      "4454 11034\n",
      "4455 513\n",
      "4456 1164\n",
      "4457 3614\n",
      "4458 13557\n",
      "4459 5253\n",
      "4460 1953\n",
      "4461 568\n",
      "4462 2690\n",
      "4463 4656\n",
      "4464 1848\n",
      "4465 1295\n",
      "4466 3549\n",
      "4467 1963\n",
      "4468 5113\n",
      "4469 920\n",
      "4470 2868\n",
      "4471 898\n",
      "4472 854\n",
      "4473 465\n",
      "4474 1108\n",
      "4475 507\n",
      "4476 588\n",
      "4477 1011\n",
      "4478 429\n",
      "4479 672\n",
      "4480 1450\n",
      "4481 321\n",
      "4482 386\n",
      "4483 2357\n",
      "4484 16607\n",
      "4485 25546\n",
      "4486 2551\n",
      "4487 1965\n",
      "4488 1581\n",
      "4489 23261\n",
      "4490 2453\n",
      "4491 1037\n",
      "4492 5512\n",
      "4493 1970\n",
      "4494 1739\n",
      "4495 2387\n",
      "4496 3202\n",
      "4497 6120\n",
      "4498 432\n",
      "4499 8634\n",
      "4500 1029\n",
      "4501 880\n",
      "4502 315\n",
      "4503 531\n",
      "4504 643\n",
      "4505 156\n",
      "4506 897\n",
      "4507 373\n",
      "4508 7125\n",
      "4509 563\n",
      "4510 573\n",
      "4511 990\n",
      "4512 1608\n",
      "4513 6054\n",
      "4514 1147\n",
      "4515 66\n",
      "4516 13725\n",
      "4517 1615\n",
      "4518 4661\n",
      "4519 10896\n",
      "4520 6228\n",
      "4521 3809\n",
      "4522 7399\n",
      "4523 3752\n",
      "4524 1757\n",
      "4525 13692\n",
      "4526 5534\n",
      "4527 1168\n",
      "4528 6598\n",
      "4529 3268\n",
      "4530 933\n",
      "4531 1838\n",
      "4532 6456\n",
      "4533 1306\n",
      "4534 1145\n",
      "4535 19002\n",
      "4536 2351\n",
      "4537 3345\n",
      "4538 3008\n",
      "4539 4744\n",
      "4540 510\n",
      "4541 2328\n",
      "4542 394\n",
      "4543 1245\n",
      "4544 92\n",
      "4545 2106\n",
      "4546 1302\n",
      "4547 816\n",
      "4548 581\n",
      "4549 345\n",
      "4550 9715\n",
      "4551 1480\n",
      "4552 458\n",
      "4553 7022\n",
      "4554 235\n",
      "4555 2969\n",
      "4556 208\n",
      "4557 225\n",
      "4558 295\n",
      "4559 24328\n",
      "4560 669\n",
      "4561 2799\n",
      "4562 1493\n",
      "4563 14420\n",
      "4564 874\n",
      "4565 534\n",
      "4566 11324\n",
      "4567 4584\n",
      "4568 2562\n",
      "4569 1428\n",
      "4570 22614\n",
      "4571 2365\n",
      "4572 10407\n",
      "4573 3571\n",
      "4574 2998\n",
      "4575 5785\n",
      "4576 4662\n",
      "4577 1167\n",
      "4578 21978\n",
      "4579 3375\n",
      "4580 1795\n",
      "4581 620\n",
      "4582 4241\n",
      "4583 7335\n",
      "4584 36\n",
      "4585 534\n",
      "4586 3901\n",
      "4587 253\n",
      "4588 1669\n",
      "4589 2396\n",
      "4590 4499\n",
      "4591 1420\n",
      "4592 1638\n",
      "4593 1498\n",
      "4594 21893\n",
      "4595 28676\n",
      "4596 3190\n",
      "4597 804\n",
      "4598 9802\n",
      "4599 16393\n",
      "4600 10238\n",
      "4601 1894\n",
      "4602 302\n",
      "4603 25815\n",
      "4604 16733\n",
      "4605 1536\n",
      "4606 1904\n",
      "4607 1562\n",
      "4608 1490\n",
      "4609 4189\n",
      "4610 4678\n",
      "4611 2699\n",
      "4612 4570\n",
      "4613 23197\n",
      "4614 1842\n",
      "4615 2367\n",
      "4616 11461\n",
      "4617 771\n",
      "4618 502\n",
      "4619 5696\n",
      "4620 2629\n",
      "4621 12822\n",
      "4622 24399\n",
      "4623 697\n",
      "4624 21108\n",
      "4625 2076\n",
      "4626 1039\n",
      "4627 12258\n",
      "4628 1626\n",
      "4629 957\n",
      "4630 1286\n",
      "4631 534\n",
      "4632 16111\n",
      "4633 552\n",
      "4634 514\n",
      "4635 871\n",
      "4636 6175\n",
      "4637 735\n",
      "4638 5176\n",
      "4639 1567\n",
      "4640 1445\n",
      "4641 1028\n",
      "4642 872\n",
      "4643 199\n",
      "4644 228\n",
      "4645 3032\n",
      "4646 5977\n",
      "4647 981\n",
      "4648 856\n",
      "4649 701\n",
      "4650 806\n",
      "4651 69\n",
      "4652 450\n",
      "4653 721\n",
      "4654 6377\n",
      "4655 427\n",
      "4656 494\n",
      "4657 689\n",
      "4658 194\n",
      "4659 1136\n",
      "4660 1879\n",
      "4661 21359\n",
      "4662 624\n",
      "4663 1618\n",
      "4664 1612\n",
      "4665 1483\n",
      "4666 9059\n",
      "4667 1465\n",
      "4668 1199\n",
      "4669 1081\n",
      "4670 753\n",
      "4671 1741\n",
      "4672 1547\n",
      "4673 6429\n",
      "4674 13850\n",
      "4675 399\n",
      "4676 8119\n",
      "4677 403\n",
      "4678 186\n",
      "4679 6960\n",
      "4680 4018\n",
      "4681 1183\n",
      "4682 392\n",
      "4683 2838\n",
      "4684 562\n",
      "4685 822\n",
      "4686 2101\n",
      "4687 894\n",
      "4688 4160\n",
      "4689 261\n",
      "4690 1658\n",
      "4691 324\n",
      "4692 1859\n",
      "4693 1633\n",
      "4694 343\n",
      "4695 225\n",
      "4696 2367\n",
      "4697 2091\n",
      "4698 3554\n",
      "4699 158\n",
      "4700 4554\n",
      "4701 238\n",
      "4702 4793\n",
      "4703 1781\n",
      "4704 290\n",
      "4705 1201\n",
      "4706 1264\n",
      "4707 736\n",
      "4708 198\n",
      "4709 22\n",
      "4710 171\n",
      "4711 766\n",
      "4712 432\n",
      "4713 458\n",
      "4714 779\n",
      "4715 288\n",
      "4716 207\n",
      "4717 1133\n",
      "4718 363\n",
      "4719 584\n",
      "4720 1788\n",
      "4721 343\n",
      "4722 1508\n",
      "4723 354\n",
      "4724 1910\n",
      "4725 4153\n",
      "4726 277\n",
      "4727 6703\n",
      "4728 3119\n",
      "4729 13455\n",
      "4730 193\n",
      "4731 856\n",
      "4732 512\n",
      "4733 1652\n",
      "4734 834\n",
      "4735 963\n",
      "4736 1380\n",
      "4737 360\n",
      "4738 1108\n",
      "4739 1333\n",
      "4740 333\n",
      "4741 959\n",
      "4742 188\n",
      "4743 2213\n",
      "4744 224\n",
      "4745 288\n",
      "4746 475\n",
      "4747 216\n",
      "4748 381\n",
      "4749 602\n",
      "4750 1000\n",
      "4751 2332\n",
      "4752 3023\n",
      "4753 1002\n",
      "4754 480\n",
      "4755 621\n",
      "4756 166\n",
      "4757 772\n",
      "4758 1606\n",
      "4759 2908\n",
      "4760 808\n",
      "4761 179\n",
      "4762 4186\n",
      "4763 17485\n",
      "4764 2773\n",
      "4765 1348\n",
      "4766 597\n",
      "4767 9394\n",
      "4768 2836\n",
      "4769 4087\n",
      "4770 1260\n",
      "4771 2196\n",
      "4772 14720\n",
      "4773 3520\n",
      "4774 2073\n",
      "4775 941\n",
      "4776 2112\n",
      "4777 560\n",
      "4778 9217\n",
      "4779 384\n",
      "4780 1605\n",
      "4781 7711\n",
      "4782 1331\n",
      "4783 797\n",
      "4784 512\n",
      "4785 489\n",
      "4786 6097\n",
      "4787 272\n",
      "4788 981\n",
      "4789 1656\n",
      "4790 542\n",
      "4791 1024\n",
      "4792 615\n",
      "4793 515\n",
      "4794 447\n",
      "4795 680\n",
      "4796 1078\n",
      "4797 1382\n",
      "4798 963\n",
      "4799 213\n",
      "4800 2281\n",
      "4801 868\n",
      "4802 1127\n",
      "4803 413\n",
      "4804 296\n",
      "4805 192\n",
      "4806 578\n",
      "4807 390\n",
      "4808 7966\n",
      "4809 132\n",
      "4810 489\n",
      "4811 2251\n",
      "4812 822\n",
      "4813 484\n",
      "4814 1939\n",
      "4815 415\n",
      "4816 3297\n",
      "4817 661\n",
      "4818 699\n",
      "4819 1028\n",
      "4820 2492\n",
      "4821 1863\n",
      "4822 1472\n",
      "4823 6256\n",
      "4824 2855\n",
      "4825 4230\n",
      "4826 1201\n",
      "4827 840\n",
      "4828 4238\n",
      "4829 2408\n",
      "4830 306\n",
      "4831 1443\n",
      "4832 548\n",
      "4833 12389\n",
      "4834 888\n",
      "4835 613\n",
      "4836 1033\n",
      "4837 1158\n",
      "4838 424\n",
      "4839 455\n",
      "4840 2502\n",
      "4841 10475\n",
      "4842 454\n",
      "4843 1243\n",
      "4844 7806\n",
      "4845 11598\n",
      "4846 727\n",
      "4847 1001\n",
      "4848 93\n",
      "4849 360\n",
      "4850 605\n",
      "4851 2764\n",
      "4852 246\n",
      "4853 1981\n",
      "4854 3768\n",
      "4855 303\n",
      "4856 415\n",
      "4857 14258\n",
      "4858 9089\n",
      "4859 749\n",
      "4860 164\n",
      "4861 708\n",
      "4862 422\n",
      "4863 2498\n",
      "4864 2643\n",
      "4865 642\n",
      "4866 484\n",
      "4867 404\n",
      "4868 1829\n",
      "4869 2777\n",
      "4870 457\n",
      "4871 1029\n",
      "4872 903\n",
      "4873 711\n",
      "4874 575\n",
      "4875 3172\n",
      "4876 1140\n",
      "4877 1115\n",
      "4878 412\n",
      "4879 760\n",
      "4880 328\n",
      "4881 289\n",
      "4882 2143\n",
      "4883 430\n",
      "4884 4201\n",
      "4885 10663\n",
      "4886 994\n",
      "4887 6011\n",
      "4888 6721\n",
      "4889 921\n",
      "4890 738\n",
      "4891 259\n",
      "4892 1373\n",
      "4893 1142\n",
      "4894 678\n",
      "4895 309\n",
      "4896 441\n",
      "4897 1021\n",
      "4898 6811\n",
      "4899 3945\n",
      "4900 8638\n",
      "4901 3354\n",
      "4902 4151\n",
      "4903 2788\n",
      "4904 5008\n",
      "4905 24585\n",
      "4906 2051\n",
      "4907 2623\n",
      "4908 6847\n",
      "4909 5616\n",
      "4910 723\n",
      "4911 10507\n",
      "4912 7506\n",
      "4913 1126\n",
      "4914 2061\n",
      "4915 13715\n",
      "4916 6196\n",
      "4917 1733\n",
      "4918 1792\n",
      "4919 1096\n",
      "4920 218\n",
      "4921 7785\n",
      "4922 676\n",
      "4923 15772\n",
      "4924 3022\n",
      "4925 15071\n",
      "4926 2416\n",
      "4927 3114\n",
      "4928 1352\n",
      "4929 4109\n",
      "4930 1320\n",
      "4931 811\n",
      "4932 296\n",
      "4933 3027\n",
      "4934 392\n",
      "4935 5750\n",
      "4936 262\n",
      "4937 680\n",
      "4938 3665\n",
      "4939 2822\n",
      "4940 659\n",
      "4941 507\n",
      "4942 4087\n",
      "4943 4657\n",
      "4944 6810\n",
      "4945 2097\n",
      "4946 435\n",
      "4947 10660\n",
      "4948 15132\n",
      "4949 5489\n",
      "4950 4739\n",
      "4951 4806\n",
      "4952 805\n",
      "4953 21133\n",
      "4954 829\n",
      "4955 2553\n",
      "4956 5214\n",
      "4957 9397\n",
      "4958 10866\n",
      "4959 6437\n",
      "4960 3081\n",
      "4961 2058\n",
      "4962 17688\n",
      "4963 14566\n",
      "4964 387\n",
      "4965 1324\n",
      "4966 1686\n",
      "4967 7578\n",
      "4968 8242\n",
      "4969 3920\n",
      "4970 922\n",
      "4971 9125\n",
      "4972 4580\n",
      "4973 6010\n",
      "4974 4324\n",
      "4975 1558\n",
      "4976 1808\n",
      "4977 3941\n",
      "4978 3209\n",
      "4979 18655\n",
      "4980 985\n",
      "4981 1421\n",
      "4982 7285\n",
      "4983 4150\n",
      "4984 3057\n",
      "4985 831\n",
      "4986 4870\n",
      "4987 779\n",
      "4988 11867\n",
      "4989 7825\n",
      "4990 3043\n",
      "4991 684\n",
      "4992 15645\n",
      "4993 5539\n",
      "4994 13550\n",
      "4995 4601\n",
      "4996 3010\n",
      "4997 467\n",
      "4998 8474\n",
      "4999 18617\n",
      "5000 1263\n",
      "5001 521\n",
      "5002 18752\n",
      "5003 1176\n",
      "5004 944\n",
      "5005 246\n",
      "5006 5764\n",
      "5007 1122\n",
      "5008 7568\n",
      "5009 2156\n",
      "5010 2444\n",
      "5011 21523\n",
      "5012 585\n",
      "5013 4287\n",
      "5014 8856\n",
      "5015 734\n",
      "5016 6367\n",
      "5017 22245\n",
      "5018 9770\n",
      "5019 4410\n",
      "5020 1361\n",
      "5021 808\n",
      "5022 1129\n",
      "5023 729\n",
      "5024 3512\n",
      "5025 1267\n",
      "5026 8758\n",
      "5027 7223\n",
      "5028 1806\n",
      "5029 13053\n",
      "5030 468\n",
      "5031 13121\n",
      "5032 7159\n",
      "5033 883\n",
      "5034 452\n",
      "5035 1458\n",
      "5036 2060\n",
      "5037 4385\n",
      "5038 2896\n",
      "5039 7517\n",
      "5040 1391\n",
      "5041 1254\n",
      "5042 952\n",
      "5043 1119\n",
      "5044 2321\n",
      "5045 2484\n",
      "5046 24052\n",
      "5047 1368\n",
      "5048 6607\n",
      "5049 1097\n",
      "5050 5466\n",
      "5051 9459\n",
      "5052 13202\n",
      "5053 1829\n",
      "5054 1544\n",
      "5055 3556\n",
      "5056 6944\n",
      "5057 4565\n",
      "5058 265\n",
      "5059 369\n",
      "5060 23622\n",
      "5061 974\n",
      "5062 1139\n",
      "5063 2062\n",
      "5064 4665\n",
      "5065 5022\n",
      "5066 122\n",
      "5067 3310\n",
      "5068 35474\n",
      "5069 10636\n",
      "5070 3522\n",
      "5071 7428\n",
      "5072 22495\n",
      "5073 3993\n",
      "5074 1802\n",
      "5075 2913\n",
      "5076 713\n",
      "5077 3801\n",
      "5078 1433\n",
      "5079 10857\n",
      "5080 4239\n",
      "5081 2347\n",
      "5082 4710\n",
      "5083 4844\n",
      "5084 6764\n",
      "5085 5289\n",
      "5086 5010\n",
      "5087 4491\n",
      "5088 5072\n",
      "5089 1359\n",
      "5090 7588\n",
      "5091 121\n",
      "5092 3742\n",
      "5093 1080\n",
      "5094 595\n",
      "5095 4620\n",
      "5096 4746\n",
      "5097 2003\n",
      "5098 4872\n",
      "5099 6255\n",
      "5100 5467\n",
      "5101 4740\n",
      "5102 2085\n",
      "5103 529\n",
      "5104 23704\n",
      "5105 6810\n",
      "5106 7431\n",
      "5107 1123\n",
      "5108 1748\n",
      "5109 4126\n",
      "5110 957\n",
      "5111 9252\n",
      "5112 11685\n",
      "5113 3539\n",
      "5114 20634\n",
      "5115 22135\n",
      "5116 2252\n",
      "5117 924\n",
      "5118 1321\n",
      "5119 5872\n",
      "5120 2354\n",
      "5121 3319\n",
      "5122 1415\n",
      "5123 4895\n",
      "5124 2830\n",
      "5125 4061\n",
      "5126 10192\n",
      "5127 2084\n",
      "5128 8273\n",
      "5129 1881\n",
      "5130 969\n",
      "5131 286\n",
      "5132 330\n",
      "5133 701\n",
      "5134 13342\n",
      "5135 3975\n",
      "5136 7588\n",
      "5137 10773\n",
      "5138 1357\n",
      "5139 410\n",
      "5140 961\n",
      "5141 2564\n",
      "5142 9151\n",
      "5143 365\n",
      "5144 7863\n",
      "5145 7864\n",
      "5146 1546\n",
      "5147 10919\n",
      "5148 5290\n",
      "5149 18831\n",
      "5150 1867\n",
      "5151 11378\n",
      "5152 3023\n",
      "5153 2203\n",
      "5154 19094\n",
      "5155 1306\n",
      "5156 5938\n",
      "5157 1295\n",
      "5158 1642\n",
      "5159 9871\n",
      "5160 4589\n",
      "5161 3049\n",
      "5162 1686\n",
      "5163 2901\n",
      "5164 6415\n",
      "5165 5295\n",
      "5166 2493\n",
      "5167 918\n",
      "5168 2772\n",
      "5169 696\n",
      "5170 726\n",
      "5171 368\n",
      "5172 1983\n",
      "5173 1658\n",
      "5174 379\n",
      "5175 2124\n",
      "5176 639\n",
      "5177 1393\n",
      "5178 1807\n",
      "5179 2414\n",
      "5180 452\n",
      "5181 2789\n",
      "5182 696\n",
      "5183 757\n",
      "5184 2940\n",
      "5185 1754\n",
      "5186 1420\n",
      "5187 12917\n",
      "5188 1923\n",
      "5189 3410\n",
      "5190 23845\n",
      "5191 2545\n",
      "5192 12936\n",
      "5193 4866\n",
      "5194 966\n",
      "5195 5601\n",
      "5196 20099\n",
      "5197 27138\n",
      "5198 290\n",
      "5199 1791\n",
      "5200 2994\n",
      "5201 13537\n",
      "5202 1866\n",
      "5203 607\n",
      "5204 2642\n",
      "5205 24725\n",
      "5206 5746\n",
      "5207 11214\n",
      "5208 2354\n",
      "5209 8530\n",
      "5210 6188\n",
      "5211 7068\n",
      "5212 440\n",
      "5213 1201\n",
      "5214 5288\n",
      "5215 1570\n",
      "5216 2294\n",
      "5217 556\n",
      "5218 2182\n",
      "5219 1396\n",
      "5220 4868\n",
      "5221 9115\n",
      "5222 8758\n",
      "5223 2622\n",
      "5224 1924\n",
      "5225 1216\n",
      "5226 5243\n",
      "5227 2676\n",
      "5228 12058\n",
      "5229 9825\n",
      "5230 13226\n",
      "5231 826\n",
      "5232 1247\n",
      "5233 22006\n",
      "5234 16498\n",
      "5235 2179\n",
      "5236 16181\n",
      "5237 1436\n",
      "5238 3999\n",
      "5239 2494\n",
      "5240 20477\n",
      "5241 8142\n",
      "5242 2945\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "5243 1181\n",
      "5244 8800\n",
      "5245 11871\n",
      "5246 8060\n",
      "5247 162\n",
      "5248 5565\n",
      "5249 2181\n",
      "5250 2125\n",
      "5251 3530\n",
      "5252 1421\n",
      "5253 3047\n",
      "5254 5331\n",
      "5255 14354\n",
      "5256 15786\n",
      "5257 5662\n",
      "5258 3610\n",
      "5259 1723\n",
      "5260 753\n",
      "5261 5904\n",
      "5262 4969\n",
      "5263 6391\n",
      "5264 1008\n",
      "5265 5125\n",
      "5266 2484\n",
      "5267 24007\n",
      "5268 3122\n",
      "5269 100\n",
      "5270 800\n",
      "5271 1498\n",
      "5272 543\n",
      "5273 1013\n",
      "5274 1954\n",
      "5275 2031\n",
      "5276 2073\n",
      "5277 3251\n",
      "5278 3589\n",
      "5279 24489\n",
      "5280 19389\n",
      "5281 2928\n",
      "5282 2189\n",
      "5283 2058\n",
      "5284 4889\n",
      "5285 1784\n",
      "5286 3999\n",
      "5287 864\n",
      "5288 6718\n",
      "5289 2077\n",
      "5290 636\n",
      "5291 19640\n",
      "5292 6659\n",
      "5293 1572\n",
      "5294 6193\n",
      "5295 937\n",
      "5296 17140\n",
      "5297 6163\n",
      "5298 36328\n",
      "5299 3075\n",
      "5300 4075\n",
      "5301 1785\n",
      "5302 2477\n",
      "5303 2346\n",
      "5304 5812\n",
      "5305 10485\n",
      "5306 24999\n",
      "5307 5065\n",
      "5308 1072\n",
      "5309 5287\n",
      "5310 7086\n",
      "5311 5317\n",
      "5312 1248\n",
      "5313 6853\n",
      "5314 14714\n",
      "5315 677\n",
      "5316 5609\n",
      "5317 2611\n",
      "5318 2064\n",
      "5319 2875\n",
      "5320 4522\n",
      "5321 12118\n",
      "5322 6832\n",
      "5323 3370\n",
      "5324 2223\n",
      "5325 24828\n",
      "5326 8360\n",
      "5327 14354\n",
      "5328 5523\n",
      "5329 25371\n",
      "5330 907\n",
      "5331 2851\n",
      "5332 468\n",
      "5333 8989\n",
      "5334 9397\n",
      "5335 1565\n",
      "5336 3914\n",
      "5337 3190\n",
      "5338 13322\n",
      "5339 6956\n",
      "5340 7575\n",
      "5341 653\n",
      "5342 824\n",
      "5343 542\n",
      "5344 2542\n",
      "5345 1442\n",
      "5346 5761\n",
      "5347 3661\n",
      "5348 276\n",
      "5349 67\n",
      "5350 8037\n",
      "5351 12114\n",
      "5352 12174\n",
      "5353 1038\n",
      "5354 15534\n",
      "5355 7816\n",
      "5356 3870\n",
      "5357 10011\n",
      "5358 22044\n",
      "5359 22084\n",
      "5360 8512\n",
      "5361 22169\n",
      "5362 19796\n",
      "5363 13679\n",
      "5364 1499\n",
      "5365 23720\n",
      "5366 22138\n",
      "5367 5770\n",
      "5368 1227\n",
      "5369 250\n",
      "5370 904\n",
      "5371 897\n",
      "5372 5654\n",
      "5373 2897\n",
      "5374 1934\n",
      "5375 22999\n",
      "5376 422\n",
      "5377 1041\n",
      "5378 1493\n",
      "5379 5242\n",
      "5380 353\n",
      "5381 1995\n",
      "5382 521\n",
      "5383 3875\n",
      "5384 23945\n",
      "5385 14057\n",
      "5386 887\n",
      "5387 5887\n",
      "5388 5157\n",
      "5389 826\n",
      "5390 6089\n",
      "5391 5944\n",
      "5392 0\n",
      "5393 372\n",
      "5394 509\n",
      "5395 3495\n",
      "5396 1965\n",
      "5397 12962\n",
      "5398 3399\n",
      "5399 4536\n",
      "5400 8984\n",
      "5401 7200\n",
      "5402 786\n",
      "5403 6145\n",
      "5404 22616\n",
      "5405 1079\n",
      "5406 1568\n",
      "5407 2054\n",
      "5408 2811\n",
      "5409 15917\n",
      "5410 1898\n",
      "5411 683\n",
      "5412 1805\n",
      "5413 664\n",
      "5414 3343\n",
      "5415 3907\n",
      "5416 2995\n",
      "5417 6291\n",
      "5418 1539\n",
      "5419 3376\n",
      "5420 18504\n",
      "5421 20173\n",
      "5422 2579\n",
      "5423 5598\n",
      "5424 26019\n",
      "5425 5163\n",
      "5426 3793\n",
      "5427 10188\n",
      "5428 1733\n",
      "5429 2653\n",
      "5430 4895\n",
      "5431 16922\n",
      "5432 1778\n",
      "5433 5147\n",
      "5434 2484\n",
      "5435 259\n",
      "5436 8965\n",
      "5437 9370\n",
      "5438 2639\n",
      "5439 5597\n",
      "5440 16463\n",
      "5441 22805\n",
      "5442 4928\n",
      "5443 7054\n",
      "5444 3103\n",
      "5445 5345\n",
      "5446 3921\n",
      "5447 5053\n",
      "5448 2437\n",
      "5449 4390\n",
      "5450 5678\n",
      "5451 854\n",
      "5452 873\n",
      "5453 21559\n",
      "5454 5533\n",
      "5455 2242\n",
      "5456 5441\n",
      "5457 5201\n",
      "5458 1873\n",
      "5459 1315\n",
      "5460 2789\n",
      "5461 17815\n",
      "5462 3941\n",
      "5463 11485\n",
      "5464 2150\n",
      "5465 25332\n",
      "5466 14554\n",
      "5467 22927\n",
      "5468 3010\n",
      "5469 2359\n",
      "5470 320\n",
      "5471 5757\n",
      "5472 4269\n",
      "5473 3441\n",
      "5474 1310\n",
      "5475 5146\n",
      "5476 2051\n",
      "5477 3551\n",
      "5478 1089\n",
      "5479 389\n",
      "5480 3605\n",
      "5481 13467\n",
      "5482 1968\n",
      "5483 23498\n",
      "5484 2803\n",
      "5485 2055\n",
      "5486 1524\n",
      "5487 3104\n",
      "5488 4559\n",
      "5489 1056\n",
      "5490 3216\n",
      "5491 3459\n",
      "5492 5844\n",
      "5493 42689\n",
      "5494 2412\n",
      "5495 256\n",
      "5496 8986\n",
      "5497 5783\n",
      "5498 9859\n",
      "5499 15998\n",
      "5500 1113\n",
      "5501 4072\n",
      "5502 1399\n",
      "5503 2941\n",
      "5504 567\n",
      "5505 3123\n",
      "5506 1178\n",
      "5507 690\n",
      "5508 257\n",
      "5509 7375\n",
      "5510 2580\n",
      "5511 2557\n",
      "5512 12033\n",
      "5513 9496\n",
      "5514 6486\n",
      "5515 5057\n",
      "5516 6129\n",
      "5517 4440\n",
      "5518 2674\n",
      "5519 832\n",
      "5520 1901\n",
      "5521 1115\n",
      "5522 1203\n",
      "5523 1869\n",
      "5524 3656\n",
      "5525 562\n",
      "5526 4470\n",
      "5527 1857\n",
      "5528 923\n",
      "5529 1444\n",
      "5530 21147\n",
      "5531 4869\n",
      "5532 6779\n",
      "5533 2608\n",
      "5534 2171\n",
      "5535 18205\n",
      "5536 688\n",
      "5537 25873\n",
      "5538 2560\n",
      "5539 1862\n",
      "5540 2587\n",
      "5541 10540\n",
      "5542 8494\n",
      "5543 1445\n",
      "5544 11105\n",
      "5545 7311\n",
      "5546 2311\n",
      "5547 1664\n",
      "5548 844\n",
      "5549 939\n",
      "5550 5449\n",
      "5551 5913\n",
      "5552 2712\n",
      "5553 6230\n",
      "5554 2036\n",
      "5555 5408\n",
      "5556 2222\n",
      "5557 3259\n",
      "5558 9964\n",
      "5559 10418\n",
      "5560 905\n",
      "5561 1758\n",
      "5562 21734\n",
      "5563 1602\n",
      "5564 3471\n",
      "5565 4221\n",
      "5566 1518\n",
      "5567 3177\n",
      "5568 5805\n",
      "5569 4838\n",
      "5570 2897\n",
      "5571 1650\n",
      "5572 8834\n",
      "5573 3067\n",
      "5574 3432\n",
      "5575 10003\n",
      "5576 4653\n",
      "5577 1465\n",
      "5578 5727\n",
      "5579 2405\n",
      "5580 1260\n",
      "5581 23530\n",
      "5582 561\n",
      "5583 9194\n",
      "5584 16480\n",
      "5585 5560\n",
      "5586 15021\n",
      "5587 4791\n",
      "5588 7916\n",
      "5589 5644\n",
      "5590 4998\n",
      "5591 21540\n",
      "5592 2325\n",
      "5593 10194\n",
      "5594 1956\n",
      "5595 5714\n",
      "5596 1055\n",
      "5597 3508\n",
      "5598 4329\n",
      "5599 24160\n",
      "5600 827\n",
      "5601 23229\n",
      "5602 20620\n",
      "5603 1180\n",
      "5604 5542\n",
      "5605 12948\n",
      "5606 5405\n",
      "5607 1761\n",
      "5608 2162\n",
      "5609 4191\n",
      "5610 8554\n",
      "5611 914\n",
      "5612 1375\n",
      "5613 3813\n",
      "5614 1161\n",
      "5615 2076\n",
      "5616 4059\n",
      "5617 2528\n",
      "5618 5334\n",
      "5619 5348\n",
      "5620 6494\n",
      "5621 1290\n",
      "5622 1996\n",
      "5623 222\n",
      "5624 1450\n",
      "5625 945\n",
      "5626 16501\n",
      "5627 12869\n",
      "5628 4391\n",
      "5629 4121\n",
      "5630 2204\n",
      "5631 7312\n",
      "5632 1793\n",
      "5633 822\n",
      "5634 1078\n",
      "5635 2541\n",
      "5636 3203\n",
      "5637 6\n",
      "5638 5603\n",
      "5639 10945\n",
      "5640 1060\n",
      "5641 1675\n",
      "5642 4546\n",
      "5643 5140\n",
      "5644 4619\n",
      "5645 4488\n",
      "5646 10221\n",
      "5647 4677\n",
      "5648 3655\n",
      "5649 25052\n",
      "5650 4269\n",
      "5651 1646\n",
      "5652 581\n",
      "5653 7491\n",
      "5654 3498\n",
      "5655 4598\n",
      "5656 24936\n",
      "5657 1251\n",
      "5658 2590\n",
      "5659 2391\n",
      "5660 23487\n",
      "5661 1076\n",
      "5662 597\n",
      "5663 1842\n",
      "5664 3756\n",
      "5665 1802\n",
      "5666 2991\n",
      "5667 1896\n",
      "5668 4831\n",
      "5669 2089\n",
      "5670 4059\n",
      "5671 1131\n",
      "5672 1283\n",
      "5673 13101\n",
      "5674 874\n",
      "5675 704\n",
      "5676 3990\n",
      "5677 6156\n",
      "5678 3752\n",
      "5679 3263\n",
      "5680 523\n",
      "5681 3595\n",
      "5682 17429\n",
      "5683 10355\n",
      "5684 4425\n",
      "5685 1685\n",
      "5686 19308\n",
      "5687 2849\n",
      "5688 592\n",
      "5689 1914\n",
      "5690 16094\n",
      "5691 396\n",
      "5692 1349\n",
      "5693 5237\n",
      "5694 11399\n",
      "5695 9416\n",
      "5696 22301\n",
      "5697 4162\n",
      "5698 10845\n",
      "5699 4771\n",
      "5700 5230\n",
      "5701 14667\n",
      "5702 1244\n",
      "5703 2675\n",
      "5704 4559\n",
      "5705 1223\n",
      "5706 4418\n",
      "5707 1497\n",
      "5708 4893\n",
      "5709 3328\n",
      "5710 503\n",
      "5711 244\n",
      "5712 3847\n",
      "5713 1156\n",
      "5714 3454\n",
      "5715 7470\n",
      "5716 9892\n",
      "5717 2914\n",
      "5718 755\n",
      "5719 25136\n",
      "5720 9193\n",
      "5721 22544\n",
      "5722 1336\n",
      "5723 2621\n",
      "5724 23114\n",
      "5725 5446\n",
      "5726 18470\n",
      "5727 3271\n",
      "5728 1483\n",
      "5729 4012\n",
      "5730 1890\n",
      "5731 1441\n",
      "5732 24596\n",
      "5733 1133\n",
      "5734 12119\n",
      "5735 19620\n",
      "5736 12144\n",
      "5737 12065\n",
      "5738 2168\n",
      "5739 2213\n",
      "5740 4739\n",
      "5741 4601\n",
      "5742 907\n",
      "5743 3859\n",
      "5744 7078\n",
      "5745 369\n",
      "5746 21166\n",
      "5747 1153\n",
      "5748 3412\n",
      "5749 3448\n",
      "5750 13569\n",
      "5751 872\n",
      "5752 3814\n",
      "5753 359\n",
      "5754 18987\n",
      "5755 2098\n",
      "5756 970\n",
      "5757 4162\n",
      "5758 1230\n",
      "5759 3119\n",
      "5760 1156\n",
      "5761 2810\n",
      "5762 2451\n",
      "5763 1007\n",
      "5764 599\n",
      "5765 5483\n",
      "5766 1891\n",
      "5767 3156\n",
      "5768 10883\n",
      "5769 1217\n",
      "5770 489\n",
      "5771 2933\n",
      "5772 20238\n",
      "5773 4723\n",
      "5774 1003\n",
      "5775 2185\n",
      "5776 2752\n",
      "5777 441\n",
      "5778 6903\n",
      "5779 2536\n",
      "5780 525\n",
      "5781 5393\n",
      "5782 1229\n",
      "5783 14471\n",
      "5784 11785\n",
      "5785 24107\n",
      "5786 5355\n",
      "5787 528\n",
      "5788 3408\n",
      "5789 789\n",
      "5790 5280\n",
      "5791 9245\n",
      "5792 1302\n",
      "5793 8048\n",
      "5794 1936\n",
      "5795 5812\n",
      "5796 1132\n",
      "5797 2402\n",
      "5798 2001\n",
      "5799 10518\n",
      "5800 1170\n",
      "5801 2091\n",
      "5802 1152\n",
      "5803 1849\n",
      "5804 1622\n",
      "5805 2836\n",
      "5806 2238\n",
      "5807 988\n",
      "5808 23104\n",
      "5809 1345\n",
      "5810 9684\n",
      "5811 477\n",
      "5812 2051\n",
      "5813 605\n",
      "5814 6665\n",
      "5815 1541\n",
      "5816 1168\n",
      "5817 544\n",
      "5818 7017\n",
      "5819 995\n",
      "5820 7091\n",
      "5821 5381\n",
      "5822 1179\n",
      "5823 6456\n",
      "5824 5092\n",
      "5825 22726\n",
      "5826 3298\n",
      "5827 689\n",
      "5828 4198\n",
      "5829 10548\n",
      "5830 9060\n",
      "5831 2106\n",
      "5832 2873\n",
      "5833 12788\n",
      "5834 12121\n",
      "5835 2893\n",
      "5836 23844\n",
      "5837 4027\n",
      "5838 4976\n",
      "5839 3717\n",
      "5840 571\n",
      "5841 1924\n",
      "5842 2465\n",
      "5843 17628\n",
      "5844 2281\n",
      "5845 743\n",
      "5846 7025\n",
      "5847 2555\n",
      "5848 3372\n",
      "5849 2142\n",
      "5850 1017\n",
      "5851 7591\n",
      "5852 26138\n",
      "5853 4726\n",
      "5854 192\n",
      "5855 23661\n",
      "5856 3349\n",
      "5857 4547\n",
      "5858 2208\n",
      "5859 4161\n",
      "5860 768\n",
      "5861 11211\n",
      "5862 3342\n",
      "5863 10880\n",
      "5864 11038\n",
      "5865 1646\n",
      "5866 1124\n",
      "5867 1111\n",
      "5868 5308\n",
      "5869 9116\n",
      "5870 24309\n",
      "5871 17601\n",
      "5872 2884\n",
      "5873 582\n",
      "5874 925\n",
      "5875 2156\n",
      "5876 23123\n",
      "5877 1420\n",
      "5878 7235\n",
      "5879 2186\n",
      "5880 4142\n",
      "5881 5934\n",
      "5882 437\n",
      "5883 2280\n",
      "5884 5063\n",
      "5885 2682\n",
      "5886 538\n",
      "5887 1821\n",
      "5888 5406\n",
      "5889 5364\n",
      "5890 682\n",
      "5891 2005\n",
      "5892 3833\n",
      "5893 6423\n",
      "5894 5158\n",
      "5895 279\n",
      "5896 2768\n",
      "5897 366\n",
      "5898 3935\n",
      "5899 5359\n",
      "5900 3866\n",
      "5901 2844\n",
      "5902 12272\n",
      "5903 2845\n",
      "5904 1053\n",
      "5905 827\n",
      "5906 1164\n",
      "5907 960\n",
      "5908 898\n",
      "5909 5259\n",
      "5910 1415\n",
      "5911 531\n",
      "5912 2505\n",
      "5913 8278\n",
      "5914 16685\n",
      "5915 10612\n",
      "5916 1539\n",
      "5917 2281\n",
      "5918 806\n",
      "5919 3025\n",
      "5920 1642\n",
      "5921 8276\n",
      "5922 1236\n",
      "5923 5116\n",
      "5924 4506\n",
      "5925 1483\n",
      "5926 2432\n",
      "5927 1766\n",
      "5928 1247\n",
      "5929 860\n",
      "5930 5124\n",
      "5931 895\n",
      "5932 5836\n",
      "5933 3538\n",
      "5934 9623\n",
      "5935 2567\n",
      "5936 2059\n",
      "5937 704\n",
      "5938 10837\n",
      "5939 1916\n",
      "5940 2662\n",
      "5941 1303\n",
      "5942 2401\n",
      "5943 2985\n",
      "5944 2650\n",
      "5945 7682\n",
      "5946 1102\n",
      "5947 1155\n",
      "5948 602\n",
      "5949 5756\n",
      "5950 1657\n",
      "5951 14146\n",
      "5952 812\n",
      "5953 1331\n",
      "5954 6393\n",
      "5955 3263\n",
      "5956 2538\n",
      "5957 5223\n",
      "5958 1570\n",
      "5959 4205\n",
      "5960 1775\n",
      "5961 3204\n",
      "5962 9967\n",
      "5963 2289\n",
      "5964 4606\n",
      "5965 14436\n",
      "5966 619\n",
      "5967 2021\n",
      "5968 21830\n",
      "5969 19501\n",
      "5970 16604\n",
      "5971 7961\n",
      "5972 814\n",
      "5973 1673\n",
      "5974 2435\n",
      "5975 2021\n",
      "5976 2031\n",
      "5977 2992\n",
      "5978 4887\n",
      "5979 16073\n",
      "5980 2890\n",
      "5981 1308\n",
      "5982 1717\n",
      "5983 644\n",
      "5984 3131\n",
      "5985 4446\n",
      "5986 6098\n",
      "5987 4057\n",
      "5988 5390\n",
      "5989 4347\n",
      "5990 1107\n",
      "5991 1938\n",
      "5992 573\n",
      "5993 9043\n",
      "5994 1565\n",
      "5995 2040\n",
      "5996 3322\n",
      "5997 2563\n",
      "5998 3932\n",
      "5999 182\n",
      "6000 687\n",
      "6001 4251\n",
      "6002 6082\n",
      "6003 3167\n",
      "6004 3096\n",
      "6005 5777\n",
      "6006 2138\n",
      "6007 5667\n",
      "6008 1379\n",
      "6009 10009\n",
      "6010 1613\n",
      "6011 740\n",
      "6012 3721\n",
      "6013 7211\n",
      "6014 1522\n",
      "6015 1605\n",
      "6016 15667\n",
      "6017 3090\n",
      "6018 4618\n",
      "6019 2351\n",
      "6020 18340\n",
      "6021 1235\n",
      "6022 785\n",
      "6023 2585\n",
      "6024 24705\n",
      "6025 1774\n",
      "6026 8462\n",
      "6027 17205\n",
      "6028 11389\n",
      "6029 18720\n",
      "6030 8908\n",
      "6031 5406\n",
      "6032 609\n",
      "6033 9113\n",
      "6034 5838\n",
      "6035 2173\n",
      "6036 1375\n",
      "6037 1927\n",
      "6038 782\n",
      "6039 7158\n",
      "6040 1966\n",
      "6041 23212\n",
      "6042 190\n",
      "6043 13553\n",
      "6044 681\n",
      "6045 184\n",
      "6046 1150\n",
      "6047 1410\n",
      "6048 25611\n",
      "6049 7063\n",
      "6050 469\n",
      "6051 9909\n",
      "6052 995\n",
      "6053 424\n",
      "6054 1201\n",
      "6055 4842\n",
      "6056 1470\n",
      "6057 675\n",
      "6058 1629\n",
      "6059 2316\n",
      "6060 1370\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "6061 909\n",
      "6062 904\n",
      "6063 6276\n",
      "6064 4157\n",
      "6065 1342\n",
      "6066 4511\n",
      "6067 5323\n",
      "6068 3904\n",
      "6069 578\n",
      "6070 2782\n",
      "6071 2864\n",
      "6072 9246\n",
      "6073 2272\n",
      "6074 10123\n",
      "6075 912\n",
      "6076 3751\n",
      "6077 2376\n",
      "6078 14579\n",
      "6079 1283\n",
      "6080 1930\n",
      "6081 17768\n",
      "6082 2510\n",
      "6083 1134\n",
      "6084 2201\n",
      "6085 4748\n",
      "6086 4716\n",
      "6087 1619\n",
      "6088 20380\n",
      "6089 4899\n",
      "6090 5410\n",
      "6091 417\n",
      "6092 11232\n",
      "6093 12686\n",
      "6094 16650\n",
      "6095 14492\n",
      "6096 14778\n",
      "6097 1374\n",
      "6098 1728\n",
      "6099 1951\n",
      "6100 1079\n",
      "6101 2961\n",
      "6102 6101\n",
      "6103 5714\n",
      "6104 3016\n",
      "6105 6693\n",
      "6106 397\n",
      "6107 6834\n",
      "6108 6918\n",
      "6109 10373\n",
      "6110 815\n",
      "6111 2765\n",
      "6112 16159\n",
      "6113 1131\n",
      "6114 5157\n",
      "6115 4589\n",
      "6116 5097\n",
      "6117 955\n",
      "6118 351\n",
      "6119 5670\n",
      "6120 5156\n",
      "6121 21548\n",
      "6122 2852\n",
      "6123 1144\n",
      "6124 12632\n",
      "6125 1244\n",
      "6126 865\n",
      "6127 3455\n",
      "6128 4895\n",
      "6129 1283\n",
      "6130 15167\n",
      "6131 10827\n",
      "6132 21108\n",
      "6133 437\n",
      "6134 3791\n",
      "6135 928\n",
      "6136 11028\n",
      "6137 8881\n",
      "6138 2189\n",
      "6139 1728\n",
      "6140 735\n",
      "6141 828\n",
      "6142 4085\n",
      "6143 8213\n",
      "6144 2444\n",
      "6145 8819\n",
      "6146 1004\n",
      "6147 1449\n",
      "6148 682\n",
      "6149 1475\n",
      "6150 9576\n",
      "6151 3268\n",
      "6152 1517\n",
      "6153 2801\n",
      "6154 907\n",
      "6155 2806\n",
      "6156 1145\n",
      "6157 4581\n",
      "6158 3748\n",
      "6159 3611\n",
      "6160 2292\n",
      "6161 4508\n",
      "6162 728\n",
      "6163 7351\n",
      "6164 1475\n",
      "6165 7023\n",
      "6166 982\n",
      "6167 4189\n",
      "6168 1812\n",
      "6169 5921\n",
      "6170 3058\n",
      "6171 2010\n",
      "6172 23847\n",
      "6173 2688\n",
      "6174 15103\n",
      "6175 2030\n",
      "6176 4152\n",
      "6177 1078\n",
      "6178 273\n",
      "6179 1433\n",
      "6180 5403\n",
      "6181 3491\n",
      "6182 1321\n",
      "6183 22454\n",
      "6184 3580\n",
      "6185 4454\n",
      "6186 4985\n",
      "6187 2054\n",
      "6188 4844\n",
      "6189 7296\n",
      "6190 1756\n",
      "6191 2048\n",
      "6192 12791\n",
      "6193 1128\n",
      "6194 12406\n",
      "6195 3011\n",
      "6196 1027\n",
      "6197 23755\n",
      "6198 2037\n",
      "6199 4766\n",
      "6200 2712\n",
      "6201 1133\n",
      "6202 457\n",
      "6203 6980\n",
      "6204 3037\n",
      "6205 5233\n",
      "6206 10358\n",
      "6207 6817\n",
      "6208 4433\n",
      "6209 11019\n",
      "6210 19470\n",
      "6211 3372\n",
      "6212 1146\n",
      "6213 826\n",
      "6214 2103\n",
      "6215 4769\n",
      "6216 280\n",
      "6217 386\n",
      "6218 2226\n",
      "6219 18942\n",
      "6220 5407\n",
      "6221 3481\n",
      "6222 4925\n",
      "6223 1577\n",
      "6224 13451\n",
      "6225 6332\n",
      "6226 2065\n",
      "6227 18066\n",
      "6228 24217\n",
      "6229 2705\n",
      "6230 6497\n",
      "6231 2912\n",
      "6232 1309\n",
      "6233 953\n",
      "6234 3383\n",
      "6235 15183\n",
      "6236 2587\n",
      "6237 3603\n",
      "6238 23471\n",
      "6239 2925\n",
      "6240 945\n",
      "6241 2927\n",
      "6242 2413\n",
      "6243 20723\n",
      "6244 4864\n",
      "6245 2300\n",
      "6246 3336\n",
      "6247 19940\n",
      "6248 9785\n",
      "6249 11166\n",
      "6250 541\n",
      "6251 11585\n",
      "6252 3842\n",
      "6253 882\n",
      "6254 3121\n",
      "6255 2934\n",
      "6256 2182\n",
      "6257 13427\n",
      "6258 25168\n",
      "6259 733\n",
      "6260 640\n",
      "6261 1117\n",
      "6262 9326\n",
      "6263 4427\n",
      "6264 689\n",
      "6265 1042\n",
      "6266 1142\n",
      "6267 3922\n",
      "6268 10423\n",
      "6269 10725\n",
      "6270 3569\n",
      "6271 14515\n",
      "6272 4269\n",
      "6273 7746\n",
      "6274 2827\n",
      "6275 7893\n",
      "6276 2090\n",
      "6277 21073\n",
      "6278 4822\n",
      "6279 3032\n",
      "6280 514\n",
      "6281 847\n",
      "6282 833\n",
      "6283 2042\n",
      "6284 1129\n",
      "6285 1166\n",
      "6286 5059\n",
      "6287 5748\n",
      "6288 1026\n",
      "6289 23705\n",
      "6290 12589\n",
      "6291 1295\n",
      "6292 6655\n",
      "6293 2899\n",
      "6294 830\n",
      "6295 6273\n",
      "6296 15596\n",
      "6297 822\n",
      "6298 2116\n",
      "6299 2706\n",
      "6300 3203\n",
      "6301 6007\n",
      "6302 11603\n",
      "6303 20630\n",
      "6304 832\n",
      "6305 1277\n",
      "6306 9413\n",
      "6307 1082\n",
      "6308 1939\n",
      "6309 941\n",
      "6310 2916\n",
      "6311 6263\n",
      "6312 11495\n",
      "6313 1098\n",
      "6314 25221\n",
      "6315 764\n",
      "6316 12414\n",
      "6317 898\n",
      "6318 2983\n",
      "6319 2686\n",
      "6320 1541\n",
      "6321 2872\n",
      "6322 3285\n",
      "6323 1555\n",
      "6324 12138\n",
      "6325 5764\n",
      "6326 22048\n",
      "6327 1051\n",
      "6328 9065\n",
      "6329 2499\n",
      "6330 31043\n",
      "6331 18607\n",
      "6332 433\n",
      "6333 1267\n",
      "6334 1449\n",
      "6335 25474\n",
      "6336 1282\n",
      "6337 4386\n",
      "6338 23633\n",
      "6339 5099\n",
      "6340 503\n",
      "6341 10904\n",
      "6342 3005\n",
      "6343 366\n",
      "6344 2137\n",
      "6345 4276\n",
      "6346 1547\n",
      "6347 8485\n",
      "6348 321\n",
      "6349 537\n",
      "6350 4665\n",
      "6351 6617\n",
      "6352 1543\n",
      "6353 1748\n",
      "6354 2147\n",
      "6355 2287\n",
      "6356 2600\n",
      "6357 1298\n",
      "6358 3069\n",
      "6359 22771\n",
      "6360 2824\n",
      "6361 962\n",
      "6362 4513\n",
      "6363 4005\n",
      "6364 466\n",
      "6365 1152\n",
      "6366 2361\n",
      "6367 1115\n",
      "6368 923\n",
      "6369 7196\n",
      "6370 11351\n",
      "6371 11432\n",
      "6372 6888\n",
      "6373 3778\n",
      "6374 1902\n",
      "6375 3447\n",
      "6376 3695\n",
      "6377 13762\n"
     ]
    }
   ],
   "source": [
    "import nltk\n",
    "import re\n",
    "from nltk.tokenize import RegexpTokenizer\n",
    "from nltk.corpus import stopwords\n",
    "tokenizer = RegexpTokenizer(r'\\w+')\n",
    "termindex = 1\n",
    "docindex = 1\n",
    "termposition=0\n",
    "pattern = re.compile(r'\\b(' + r'|'.join(stopwords.words('english')) + r')\\b\\s*') # Removing Stop Words\n",
    "for txt in files:\n",
    "    termposition=0\n",
    "    add_to_docids(txt,docindex)\n",
    "    docindex = docindex+1\n",
    "    contents = \"\"\n",
    "    with open(txt,'r', encoding='utf8', errors='ignore') as f:\n",
    "        for line in f.readlines():\n",
    "            contents += line\n",
    "        contents_lower_case = convert_lower_case(contents)\n",
    "        contents_without_numbers = re.sub(r'\\d+', '', contents_lower_case) # Removing Numbers\n",
    "        contents_without_stop_words = pattern.sub('', contents_without_numbers)\n",
    "        tokens = tokenizer.tokenize(contents_without_stop_words)\n",
    "        print(docindex-1,len(tokens))\n",
    "        for word in tokens:\n",
    "            termposition=termposition+1\n",
    "            if word.isalpha():\n",
    "                strip_word=word.strip()\n",
    "                if not strip_word.isspace():\n",
    "                    if len(strip_word)>1:\n",
    "                        word_stemming = apply_stemming(strip_word)\n",
    "                        if check_termid(word_stemming):\n",
    "                          termid=get_termid(word_stemming)\n",
    "                          add_to_term_index_list(termid,docindex-1,termposition)\n",
    "                          update_term_index(termid,docindex-1,termposition)\n",
    "                        else:\n",
    "                          add_to_term_index_list(termindex,docindex-1,termposition)\n",
    "                          add_to_term_index(termindex,docindex-1,termposition)\n",
    "                          add_to_termids(word_stemming,termindex)\n",
    "                          termindex=termindex+1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# MergeSort Function For Creating Sorted Term, Doc ID pair"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [],
   "source": [
    "def mergeSort(temp): \n",
    "    if len(temp) >1: \n",
    "        mid = len(temp)//2 \n",
    "        L = temp[:mid] \n",
    "        R = temp[mid:] \n",
    "  \n",
    "        mergeSort(L) \n",
    "        mergeSort(R) \n",
    "  \n",
    "        i = j = k = 0\n",
    "          \n",
    "        while i < len(L) and j < len(R):\n",
    "            L_values=L[i]\n",
    "            R_values=R[j]\n",
    "            if L_values[0] < R_values[0]: \n",
    "                temp[k] = L[i] \n",
    "                i+=1\n",
    "            elif L_values[0]>R_values[0]: \n",
    "                temp[k] = R[j] \n",
    "                j+=1\n",
    "            elif L_values[0]==R_values[0]:\n",
    "                if L_values[1]<R_values[1]:\n",
    "                    temp[k] = L[i] \n",
    "                    i+=1\n",
    "                elif L_values[1]>R_values[1]:\n",
    "                    temp[k] = R[j] \n",
    "                    j+=1\n",
    "                elif L_values[1]==R_values[1]:\n",
    "                    if L_values[2]<R_values[2]:\n",
    "                        temp[k] = L[i] \n",
    "                        i+=1\n",
    "                    elif L_values[2]>=R_values[2]:\n",
    "                        temp[k] = R[j] \n",
    "                        j+=1    \n",
    "            k+=1\n",
    "          \n",
    "        while i < len(L): \n",
    "            temp[k] = L[i] \n",
    "            i+=1\n",
    "            k+=1\n",
    "          \n",
    "        while j < len(R): \n",
    "            temp[k] = R[j] \n",
    "            j+=1\n",
    "            k+=1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Calling Merge Sort Function"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [],
   "source": [
    "new_list = term_index_list.copy()\n",
    "mergeSort(new_list)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Function For Creating Posting"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [],
   "source": [
    "def create_posting(posting_list):\n",
    " new_temp_list=[]\n",
    " new_term_index_list=[]\n",
    " term_index_values=posting_list[0]\n",
    " temp_index=[term_index_values[0],1,1,term_index_values[1],term_index_values[2]]\n",
    " new_temp_list=new_temp_list+temp_index\n",
    " temp_index.clear()\n",
    " length_list=len(posting_list)\n",
    " for i in range(1,length_list):\n",
    "     length=len(new_temp_list)\n",
    "     term_index_values=posting_list[i]\n",
    "     if term_index_values[0]==new_temp_list[0]:\n",
    "         new_temp_list[1]+=1\n",
    "         if term_index_values[1]!=new_temp_list[length-2]:\n",
    "             new_temp_list[2]+=1\n",
    "         temp_index=[term_index_values[1],term_index_values[2]]\n",
    "         new_temp_list=new_temp_list+temp_index\n",
    "         temp_index.clear()\n",
    "     else:\n",
    "         new_term_index_list.append(new_temp_list.copy())\n",
    "         new_temp_list.clear()\n",
    "         temp_index=[term_index_values[0],1,1,term_index_values[1],term_index_values[2]]\n",
    "         new_temp_list=new_temp_list+temp_index\n",
    "         temp_index.clear()\n",
    " return new_term_index_list"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Calling Create Posting"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [],
   "source": [
    "term_index_list=create_posting(new_list)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# For Creating docids.txt file"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [],
   "source": [
    "f= open(\"docids.txt\",\"w+\")\n",
    "for key,val in docids.items():\n",
    "    f.write(str(val))\n",
    "    f.write('\\t')\n",
    "    f.write(key)\n",
    "    f.write('\\n')\n",
    "f.close()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# For Creating termids.txt file"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [],
   "source": [
    "f= open(\"termids.txt\",\"w+\")\n",
    "for key,val in termids.items():\n",
    "    f.write(str(val))\n",
    "    f.write('\\t')\n",
    "    f.write(key)\n",
    "    f.write('\\n')\n",
    "f.close()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# For Creating term_index.txt file With Delta Encoding"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {
    "scrolled": false
   },
   "outputs": [],
   "source": [
    "f=open(\"term_index.txt\",\"w+\")\n",
    "for key,val in term_index.items():\n",
    "    f.write(str(key))\n",
    "    f.write(' ')\n",
    "    length=len(val)\n",
    "    p_docid=val[2]\n",
    "    p_term_pos=val[3]\n",
    "    for i in range(4,length,2):\n",
    "        n_docid=val[i]\n",
    "        n_term_pos=val[i+1]\n",
    "        val[i]=n_docid-p_docid\n",
    "        if val[i]==0:\n",
    "            val[i+1]=n_term_pos-p_term_pos\n",
    "        p_docid=n_docid\n",
    "        p_term_pos=n_term_pos\n",
    "    k=1\n",
    "    for v in val:\n",
    "        f.write(str(v))\n",
    "        if k==1 or k==2 or k%2==0:\n",
    "            f.write(' ')\n",
    "        else:\n",
    "            f.write(',')\n",
    "        k+=1\n",
    "    f.write('\\n')\n",
    "f.close()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Reading Index for Statistics "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# For Retrieving termids.txt file"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [],
   "source": [
    "new_termids=dict()\n",
    "f=open(\"termids.txt\",\"r\",encoding='ansi', errors='ignore')\n",
    "for line in f.readlines():\n",
    "    contents = line\n",
    "    word=contents.split()\n",
    "    new_termids[word[1]]=int(word[0])\n",
    "f.close()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# For Retrieving term_index.txt file"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [],
   "source": [
    "import re\n",
    "new_term_index=dict()\n",
    "f=open(\"term_index.txt\",\"r\",encoding='utf8', errors='ignore')\n",
    "key=0\n",
    "val=[]\n",
    "for line in f.readlines():\n",
    "    contents = line\n",
    "    word=re.split(' |,',contents)\n",
    "    word.pop(-1)\n",
    "    key=int(word[0])\n",
    "    val=[]\n",
    "    for txt in word[1:]:\n",
    "        val.append(int(txt))\n",
    "    new_term_index[key]=val\n",
    "    #print (key, val)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# For Getting Relevant Information About Input Word\n",
    "\n",
    "Like termid,number of documents present in and number of occurences"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "center\n",
      "TERMID:  5\n",
      "Number of documents containing term:  3221\n",
      "Term frequency in corpus:  21461\n"
     ]
    }
   ],
   "source": [
    " word = input()\n",
    " word_lower_case = convert_lower_case(word)\n",
    " word_stemming = apply_stemming(word_lower_case)\n",
    " if word_stemming in new_termids:\n",
    "    termindex=new_termids.get(word_stemming)\n",
    "    val=new_term_index.get(termindex)\n",
    "    print(\"TERMID: \",termindex)\n",
    "    print(\"Number of documents containing term: \",val[1])\n",
    "    print(\"Term frequency in corpus: \",val[0])\n",
    " else:\n",
    "    print (\"No Word Found\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Exporting Data/ Plotting word frequency graph and word - log frequency graph"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [],
   "source": [
    "import matplotlib.pyplot as plt\n",
    "import csv\n",
    "\n",
    "with open('word-frequency.csv', 'w', newline='') as file:\n",
    "    writer = csv.writer(file)\n",
    "    for word,key in new_termids.items():\n",
    "        termindex=new_termids.get(word)\n",
    "        val=new_term_index.get(termindex)        \n",
    "        writer.writerow([word, val[0]])                      \n",
    "file.close()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}