{"trustable":false,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cstyle type\u003d\"text/css\"\u003e\r\nh1,h2,h3,h4,h5,h6{margin-bottom:0;}div.textBG p{margin: 0 0 0.0001pt;}\u003c/style\u003e\r\n\u003cp\u003e\r\n\t\u003cspan style\u003d\"float:right\"\u003e\u003ca href\u003d\"http://livearchive.onlinejudge.org/external/58/5881.pdf\" target\u003d\"_blank\"\u003e\u003cimg alt\u003d\"Download as PDF\" border\u003d\"0\" height\u003d\"26\" src\u003d\"http://livearchive.onlinejudge.org/components/com_onlinejudge/images/button_pdf.png\" title\u003d\"Download as PDF\" width\u003d\"100\" /\u003e\u003c/a\u003e\u003c/span\u003e\u003c/p\u003e\r\n\u003cdiv style\u003d\"clear:both\"\u003e\r\n\t\u0026nbsp;\u003c/div\u003e\r\n\u003cp\u003e\r\n\tThe security of many ciphers strongly depends on the fact that the keys are unique and never re-used. This may be vitally important, since a relatively strong cipher may be broken if the same key is used to encrypt several different messages.\u003c/p\u003e\r\n\u003cp\u003e\r\n\tIn this problem, we will try to detect repeating (duplicate) usage of keys. Given a sequence of keys used to encrypt messages, your task is to determine what keys have been used repeatedly in some specified period.\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003e\r\n\tThe input contains several cipher descriptions. Each description starts with one line containing two integer numbers \u003cspan class\u003d\"MATH\"\u003e\u003ci\u003eM\u003c/i\u003e\u003c/span\u003e and \u003cspan class\u003d\"MATH\"\u003e\u003ci\u003eQ\u003c/i\u003e\u003c/span\u003e separated by a space. \u003cspan class\u003d\"MATH\"\u003e\u003ci\u003eM\u003c/i\u003e\u003c/span\u003e \u003c!-- MATH\r\n $(1 \\le M \\le 1 000 000)$\r\n --\u003e\u003cspan class\u003d\"MATH\"\u003e(\u003cspan data-scayt_word\u003d\"1M1000000\" data-scaytid\u003d\"1\"\u003e1\u003cimg align\u003d\"MIDDLE\" alt\u003d\"$ \\le$\" border\u003d\"0\" height\u003d\"31\" src\u003d\"http://livearchive.onlinejudge.org/external/58/5881img1.png\" width\u003d\"18\" /\u003e\u003ci\u003eM\u003c/i\u003e\u003cimg align\u003d\"MIDDLE\" alt\u003d\"$ \\le$\" border\u003d\"0\" height\u003d\"31\" src\u003d\"http://livearchive.onlinejudge.org/external/58/5881img1.png\" width\u003d\"18\" /\u003e1000000\u003c/span\u003e)\u003c/span\u003e is the number of encrypted messages, \u003cspan class\u003d\"MATH\"\u003e\u003ci\u003eQ\u003c/i\u003e\u003c/span\u003e is the number of queries \u003c!-- MATH\r\n $(0 \\le Q \\le 1 000 000)$\r\n --\u003e\u003cspan class\u003d\"MATH\"\u003e(0\u003cimg align\u003d\"MIDDLE\" alt\u003d\"$ \\le$\" border\u003d\"0\" height\u003d\"31\" src\u003d\"http://livearchive.onlinejudge.org/external/58/5881img1.png\" width\u003d\"18\" /\u003e\u003cspan data-scayt_word\u003d\"Q1000000\" data-scaytid\u003d\"2\"\u003e\u003ci\u003eQ\u003c/i\u003e\u003cimg align\u003d\"MIDDLE\" alt\u003d\"$ \\le$\" border\u003d\"0\" height\u003d\"31\" src\u003d\"http://livearchive.onlinejudge.org/external/58/5881img1.png\" width\u003d\"18\" /\u003e1000000\u003c/span\u003e)\u003c/span\u003e.\u003c/p\u003e\r\n\u003cp\u003e\r\n\tEach of the following \u003cspan class\u003d\"MATH\"\u003e\u003ci\u003eM\u003c/i\u003e\u003c/span\u003e lines contains one number \u003cspan class\u003d\"MATH\"\u003e\u003cspan data-scayt_word\u003d\"Ki\" data-scaytid\u003d\"3\"\u003e\u003ci\u003eK\u003c/i\u003e\u003csub\u003ei\u003c/sub\u003e\u003c/span\u003e\u003c/span\u003e \u003c!-- MATH\r\n $(0 \\le K_{i} \\le 2^{30})$\r\n --\u003e\u003cspan class\u003d\"MATH\"\u003e(\u003cspan data-scayt_word\u003d\"0Ki230\" data-scaytid\u003d\"4\"\u003e0\u003cimg align\u003d\"MIDDLE\" alt\u003d\"$ \\le$\" border\u003d\"0\" height\u003d\"31\" src\u003d\"http://livearchive.onlinejudge.org/external/58/5881img1.png\" width\u003d\"18\" /\u003e\u003ci\u003eK\u003c/i\u003e\u003csub\u003ei\u003c/sub\u003e\u003cimg align\u003d\"MIDDLE\" alt\u003d\"$ \\le$\" border\u003d\"0\" height\u003d\"31\" src\u003d\"http://livearchive.onlinejudge.org/external/58/5881img1.png\" width\u003d\"18\" /\u003e2\u003csup\u003e30\u003c/sup\u003e\u003c/span\u003e)\u003c/span\u003e specifying the identifier of a key used to encrypt the \u003cspan data-scayt_word\u003d\"i-th\" data-scaytid\u003d\"12\"\u003e\u003cspan class\u003d\"MATH\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/span\u003e-th\u003c/span\u003e message. The next \u003cspan class\u003d\"MATH\"\u003e\u003ci\u003eQ\u003c/i\u003e\u003c/span\u003e lines then contain one query each. Each query is specified by two integer numbers \u003cspan class\u003d\"MATH\"\u003e\u003cspan data-scayt_word\u003d\"Bj\" data-scaytid\u003d\"10\"\u003e\u003ci\u003eB\u003c/i\u003e\u003csub\u003ej\u003c/sub\u003e\u003c/span\u003e\u003c/span\u003e and \u003cspan class\u003d\"MATH\"\u003e\u003cspan data-scayt_word\u003d\"Ej\" data-scaytid\u003d\"11\"\u003e\u003ci\u003eE\u003c/i\u003e\u003csub\u003ej\u003c/sub\u003e\u003c/span\u003e\u003c/span\u003e, \u003c!-- MATH\r\n $1 \\le B_{j} \r\n\\le E_{j} \\le M$\r\n --\u003e\u003cspan class\u003d\"MATH\"\u003e\u003cspan data-scayt_word\u003d\"1BjEjM\" data-scaytid\u003d\"15\"\u003e1\u003cimg align\u003d\"MIDDLE\" alt\u003d\"$ \\le$\" border\u003d\"0\" height\u003d\"31\" src\u003d\"http://livearchive.onlinejudge.org/external/58/5881img1.png\" width\u003d\"18\" /\u003e\u003ci\u003eB\u003c/i\u003e\u003csub\u003ej\u003c/sub\u003e\u003cimg align\u003d\"MIDDLE\" alt\u003d\"$ \\le$\" border\u003d\"0\" height\u003d\"31\" src\u003d\"http://livearchive.onlinejudge.org/external/58/5881img1.png\" width\u003d\"18\" /\u003e\u003ci\u003eE\u003c/i\u003e\u003csub\u003ej\u003c/sub\u003e\u003cimg align\u003d\"MIDDLE\" alt\u003d\"$ \\le$\" border\u003d\"0\" height\u003d\"31\" src\u003d\"http://livearchive.onlinejudge.org/external/58/5881img1.png\" width\u003d\"18\" /\u003e\u003ci\u003eM\u003c/i\u003e\u003c/span\u003e\u003c/span\u003e, giving the interval of messages we want to check.\u003c/p\u003e\r\n\u003cp\u003e\r\n\tThere is one empty line after each description. The input is terminated by a line containing two zeros in place of the numbers \u003cspan class\u003d\"MATH\"\u003e\u003ci\u003eM\u003c/i\u003e\u003c/span\u003e and \u003cspan class\u003d\"MATH\"\u003e\u003ci\u003eQ\u003c/i\u003e\u003c/span\u003e.\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003e\r\n\tFor each query, print one line of output. The line should contain the string ``\u003ctt\u003eOK\u003c/tt\u003e\u0026quot; if all keys used to encrypt messages between \u003cspan class\u003d\"MATH\"\u003e\u003cspan data-scayt_word\u003d\"Bj\" data-scaytid\u003d\"5\"\u003e\u003ci\u003eB\u003c/i\u003e\u003csub\u003ej\u003c/sub\u003e\u003c/span\u003e\u003c/span\u003e and \u003cspan class\u003d\"MATH\"\u003e\u003cspan data-scayt_word\u003d\"Ej\" data-scaytid\u003d\"6\"\u003e\u003ci\u003eE\u003c/i\u003e\u003csub\u003ej\u003c/sub\u003e\u003c/span\u003e\u003c/span\u003e (inclusive) are mutually different (that means, they have different identifiers). If some of the keys have been used repeatedly, print the identifier for the key which is repeated for the first time.\u003c/p\u003e\r\n\u003cp\u003e\r\n\tPrint one empty line after each cipher description.\u003c/p\u003e"}},{"title":"Sample Input","value":{"format":"HTML","content":"\u003cp\u003e\r\n\t\u0026nbsp;\u003c/p\u003e\r\n\u003cpre\u003e\r\n10 5\r\n3\r\n2\r\n3\r\n4\r\n9\r\n7\r\n3\r\n8\r\n4\r\n1\r\n1 3\r\n2 6\r\n4 10\r\n3 7\r\n2 6\r\n\r\n5 2\r\n1\r\n2\r\n3\r\n1\r\n2\r\n2 4\r\n1 5\r\n\r\n7 1\r\n1\r\n2\r\n3\r\n3\r\n2\r\n4\r\n4\r\n1 7\r\n\r\n0 0\r\n\u003c/pre\u003e"}},{"title":"Sample Output","value":{"format":"HTML","content":"\u003cp\u003e\r\n\t\u0026nbsp;\u003c/p\u003e\r\n\u003cpre\u003e\r\n3\r\nOK\r\n4\r\n3\r\nOK\r\nOK\r\n1\r\n3\r\n\r\n\u003c/pre\u003e"}}]}