{"problem":{"name":"D. Glad to see you!","description":{"content":"**This is an interactive problem. In the output section below you will see the information about flushing the output.** On Sunday Leha the hacker took Nura from the house where she lives and went wit","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF810D"},"statements":[{"statement_type":"Markdown","content":"**This is an interactive problem. In the output section below you will see the information about flushing the output.**\n\nOn Sunday Leha the hacker took Nura from the house where she lives and went with her to one of the most luxurious restaurants in Vičkopolis. Upon arrival, they left the car in a huge parking lot near the restaurant and hurried inside the building.\n\nIn the restaurant a polite waiter immediately brought the menu to Leha and Noora, consisting of _n_ dishes. It is interesting that all dishes in the menu are numbered with integers from 1 to _n_. After a little thought, the girl ordered exactly _k_ different dishes from available in the menu. To pass the waiting time while the chefs prepare ordered dishes, the girl invited the hacker to play a game that will help them get to know each other better.\n\nThe game itself is very simple: Noora wants Leha to guess any two dishes among all ordered. At the same time, she is ready to answer only one type of questions. Leha can say two numbers _x_ and _y_ (1 ≤ _x_, _y_ ≤ _n_). After that Noora chooses some dish _a_ for the number _x_ such that, at first, _a_ is among the dishes Noora ordered (_x_ can be equal to _a_), and, secondly, the value is the minimum possible. By the same rules the girl chooses dish _b_ for _y_. After that Noora says «_TAK_» to Leha, if , and «_NIE_» otherwise. However, the restaurant is preparing quickly, so Leha has enough time to ask no more than 60 questions. After that he should name numbers of any two dishes Noora ordered.\n\nHelp Leha to solve this problem!\n\n## Input\n\nThere are two numbers _n_ and _k_ (2 ≤ _k_ ≤ _n_ ≤ 105) in the single line of input denoting the number of dishes in the menu and the number of dishes Noora ordered.\n\n## Output\n\nIf you want to provide an answer, output a string of the form 2 _x_ _y_ (1 ≤ _x_, _y_ ≤ _n_, _x_ ≠ _y_), if you think the dishes _x_ and _y_ was among dishes ordered by Noora. After that, flush the output and terminate your program.\n\n[samples]\n\n## Interaction\n\nWhile helping Leha, you can ask queries to Noora no more than 60 times. Each query should be printed in it's own line and have the form 1 _x_ _y_ (1 ≤ _x_, _y_ ≤ _n_). You have to both print the end-of-line character and flush the output. After flushing you should read the answer for this query from input.\n\nAfter each query jury's program will print one line «_TAK_» or «_NIE_» (without quotes) in input stream depending on the girl's answer.\n\nTo flush you can use (just after printing an integer and end-of-line):\n\n*   _fflush(stdout)_ in C++;\n*   _System.out.flush()_ in Java;\n*   _stdout.flush()_ in Python;\n*   _flush(output)_ in Pascal;\n*   see the documentation for other languages.\n\n**Hacking**\n\nFor hacking you should write numbers _n_ and _k_ (2 ≤ _k_ ≤ _n_ ≤ 105) in the first line and, for describing dishes Noora ordered, _k_ different integers _a_1, _a_2, ..., _a__k_ (1 ≤ _a__i_ ≤ _n_), _written in ascending order_ in the second line. Of course, solution you want to hack won't be able to read the numbers of ordered dishes.\n\n## Note\n\nThere are three dishes in sample. Noora ordered dished numberes 2 and 3, which Leha should guess. If Noora receive requests for the first dish (_x_ = 1), then she'll choose the second dish (_a_ = 2) as the dish with the minimum value . For the second (_x_ = 2) and the third (_x_ = 3) dishes themselves will be optimal, because in that case .\n\nLet Leha asks Noora about the next couple of dishes:\n\n*   _x_ = 1, _y_ = 2, then he'll recieve «_NIE_» answer, because |1 - 2| > |2 - 2|\n*   _x_ = 2, _y_ = 1, then he'll recieve «_TAK_» answer, because |2 - 2| ≤ |1 - 2|\n*   _x_ = 1, _y_ = 3, then he'll recieve «_NIE_» answer, because |1 - 2| > |3 - 3|\n*   _x_ = 3, _y_ = 1, then he'll recieve «_TAK_» answer, because |3 - 3| ≤ |1 - 2|\n*   _x_ = 2, _y_ = 3, then he'll recieve «_TAK_» answer, because |2 - 2| ≤ |3 - 3|\n*   _x_ = 3, _y_ = 2, then he'll recieve «_TAK_» answer, because |3 - 3| ≤ |2 - 2|\n\nAccording to the available information, it is possible to say that Nura ordered dishes with numbers 2 and 3.","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"*这是一个交互式问题。在下面的输出部分，你将看到有关刷新输出的信息。*\n\n星期天，黑客 Leha 带着 Nura 离开她居住的房屋，前往 Vičkopolis 最豪华的餐厅之一。到达后，他们将车停在餐厅附近巨大的停车场，然后匆匆进入大楼。\n\n在餐厅里，一位礼貌的侍者立即将菜单递给 Leha 和 Noora，菜单上有 #cf_span[n] 道菜。有趣的是，菜单上的所有菜品都用从 #cf_span[1] 到 #cf_span[n] 的整数编号。经过一番思考，女孩从菜单中点选了恰好 #cf_span[k] 道不同的菜。为了在厨师准备菜品的等待时间里打发时光，女孩邀请黑客玩一个游戏，以更好地了解彼此。\n\n游戏本身非常简单：Noora 希望 Leha 猜出她所点的任意两道菜。同时，她只愿意回答一种类型的问题。Leha 可以说出两个数字 #cf_span[x] 和 #cf_span[y] #cf_span[(1 ≤ x, y ≤ n)]。之后，Noora 会为数字 #cf_span[x] 选择一道菜 #cf_span[a]，使得：第一，#cf_span[a] 属于 Noora 所点的菜之一（#cf_span[x] 可以等于 #cf_span[a]）；第二，值  是最小可能的。同样地，女孩为 #cf_span[y] 选择一道菜 #cf_span[b]。之后，Noora 会告诉 Leha «_TAK_»（是），如果 ，否则告诉 «_NIE_»（否）。然而，餐厅准备得很快，因此 Leha 只有足够的时间提出不超过 #cf_span[60] 次询问。之后，他必须说出 Noora 所点的任意两道菜的编号。\n\n帮助 Leha 解决这个问题！\n\n输入的一行包含两个数字 #cf_span[n] 和 #cf_span[k] #cf_span[(2 ≤ k ≤ n ≤ 105)]，分别表示菜单中的菜品数量和 Noora 点选的菜品数量。\n\n如果你想给出答案，请输出一行形如 #cf_span[2] #cf_span[x] #cf_span[y] #cf_span[(1 ≤ x, y ≤ n, x ≠ y)] 的字符串，表示你认为菜品 #cf_span[x] 和 #cf_span[y] 是 Noora 点选的。之后，刷新输出并终止你的程序。\n\n在帮助 Leha 时，你可以向 Noora 提问最多 #cf_span[60] 次。每次查询应单独占一行，格式为 #cf_span[1] #cf_span[x] #cf_span[y] #cf_span[(1 ≤ x, y ≤ n)]。你必须同时打印换行符并刷新输出。刷新后，你需要从输入中读取该查询的答案。\n\n每次查询后，评测程序将在输入流中输出一行 «_TAK_» 或 «_NIE_»（不含引号），取决于女孩的回答。\n\n要刷新输出，你可以在（打印整数和换行符后）使用：\n\n*Cheat（黑客攻击）*\n\n要进行黑客攻击，你应在第一行写入数字 #cf_span[n] 和 #cf_span[k] #cf_span[(2 ≤ k ≤ n ≤ 105)]，并在第二行写入 #cf_span[k] 个不同的整数 #cf_span[a1, a2, ..., ak] #cf_span[(1 ≤ ai ≤ n)]，按**升序排列**。当然，你想要黑客攻击的解决方案无法读取所点菜品的编号。\n\n## Input\n\n输入的一行包含两个数字 #cf_span[n] 和 #cf_span[k] #cf_span[(2 ≤ k ≤ n ≤ 105)]，分别表示菜单中的菜品数量和 Noora 点选的菜品数量。\n\n## Output\n\n如果你想给出答案，请输出一行形如 #cf_span[2] #cf_span[x] #cf_span[y] #cf_span[(1 ≤ x, y ≤ n, x ≠ y)] 的字符串，表示你认为菜品 #cf_span[x] 和 #cf_span[y] 是 Noora 点选的。之后，刷新输出并终止你的程序。\n\n[samples]\n\n## Interaction\n\n在帮助 Leha 时，你可以向 Noora 提问最多 #cf_span[60] 次。每次查询应单独占一行，格式为 #cf_span[1] #cf_span[x] #cf_span[y] #cf_span[(1 ≤ x, y ≤ n)]。你必须同时打印换行符并刷新输出。刷新后，你需要从输入中读取该查询的答案。每次查询后，评测程序将在输入流中输出一行 «_TAK_» 或 «_NIE_»（不含引号），取决于女孩的回答。要刷新输出，你可以在（打印整数和换行符后）使用： _fflush(stdout)_ 在 C++ 中；_System.out.flush()_ 在 Java 中；_stdout.flush()_ 在 Python 中；_flush(output)_ 在 Pascal 中；其他语言请参阅文档。*Cheat（黑客攻击）*要进行黑客攻击，你应在第一行写入数字 #cf_span[n] 和 #cf_span[k] #cf_span[(2 ≤ k ≤ n ≤ 105)]，并在第二行写入 #cf_span[k] 个不同的整数 #cf_span[a1, a2, ..., ak] #cf_span[(1 ≤ ai ≤ n)]，按**升序排列**。当然，你想要黑客攻击的解决方案无法读取所点菜品的编号。\n\n## Note\n\n在样例中，共有三道菜。Noora 点选了编号为 #cf_span[2] 和 #cf_span[3] 的菜，Leha 需要猜出它们。如果 Noora 收到关于第一道菜（#cf_span[x = 1]）的请求，她会选择第二道菜（#cf_span[a = 2]）作为使  值最小的菜。对于第二道（#cf_span[x = 2]）和第三道（#cf_span[x = 3]）菜本身是最优的，因为此时 。\n\n假设 Leha 向 Noora 提问以下几对菜品：\n\n根据已有信息，可以推断出 Nura 点选的菜是编号为 #cf_span[2] 和 #cf_span[3] 的菜。\n\n当 Leha 询问 #cf_span[x = 1], #cf_span[y = 2] 时，他会收到 «_NIE_» 的回答，因为 #cf_span[|1 - 2| > |2 - 2|]；\n当 Leha 询问 #cf_span[x = 2], #cf_span[y = 1] 时，他会收到 «_TAK_» 的回答，因为 #cf_span[|2 - 2| ≤ |1 - 2|]；\n当 Leha 询问 #cf_span[x = 1], #cf_span[y = 3] 时，他会收到 «_NIE_» 的回答，因为 #cf_span[|1 - 2| > |3 - 3|]；\n当 Leha 询问 #cf_span[x = 3], #cf_span[y = 1] 时，他会收到 «_TAK_» 的回答，因为 #cf_span[|3 - 3| ≤ |1 - 2|]；\n当 Leha 询问 #cf_span[x = 2], #cf_span[y = 3] 时，他会收到 «_TAK_» 的回答，因为 #cf_span[|2 - 2| ≤ |3 - 3|]；\n当 Leha 询问 #cf_span[x = 3], #cf_span[y = 2] 时，他会收到 «_TAK_» 的回答，因为 #cf_span[|3 - 3| ≤ |2 - 2|]。\n\n根据已有信息，可以推断出 Nura 点选的菜是编号为 #cf_span[2] 和 #cf_span[3] 的菜。","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ n, k \\in \\mathbb{Z} $ with $ 2 \\leq k \\leq n \\leq 10^5 $.  \nLet $ S \\subseteq \\{1, 2, \\dots, n\\} $ be the unknown set of $ k $ ordered dishes.  \nFor any $ x \\in \\{1, 2, \\dots, n\\} $, define $ f(x) = \\min \\{ a \\in S \\mid a \\geq x \\} $.  \n\n**Constraints**  \n1. $ |S| = k $  \n2. Leha may ask at most 60 queries of the form $ (x, y) $, where each query returns:  \n   $$\n   \\texttt{TAK} \\iff f(x) \\leq f(y), \\quad \\texttt{NIE} \\iff f(x) > f(y)\n   $$\n\n**Objective**  \nIdentify any two distinct elements $ x, y \\in S $ using at most 60 queries.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF810D","tags":["binary search","interactive"],"sample_group":[["3 2\nNIE\nTAK\nNIE\nTAK\nTAK\nTAK","1 1 2\n1 2 1\n1 1 3\n1 3 1\n1 2 3\n1 3 2\n2 2 3"]],"created_at":"2026-03-03 11:00:39"}}