{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":" Nod Ishimatsu is a student majoring computer science. He has wrote a program that performs hierarchical clustering, for the end-term project in a class of \u003ci\u003eIntroduction to Artificial Intellegence\u003c/i\u003e. Clustering is the process of grouping a set of objects into subsets called \u003ci\u003eclusters\u003c/i\u003e, so that each cluster contains those similar in some sense. Hierarchical clustering is a way to do this indirectly; it produces trees (or in this problem collections of trees) called \u003ci\u003edendrograms\u003c/i\u003e. A dendrogram represents similarity among objects. The figure below shows an example dendrogram. \u003cbr\u003e \u003ccenter\u003e \u003cimg src\u003d\"CDN_BASE_URL/648319c57c3f0d8cfd3050cdb16cd21f?v\u003d1715982720\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e \u003c/center\u003e \u003cbr\u003e Leaves (at the bottom) denote objects. The horizontal lines split the objects into two or more subgroups and indicate objects in different subgroups are less similar than those in the same subgroup. Thus, basically, the upper the line is located, the less similar the objects or the sets of objects connected by it. We can have, for example, three clusters by using the top two horizontal lines. Nod\u0027s program also outputs dendrograms, but it has two problems. Firstly, output dendrograms are sometimes not fully connected, i.e. output can contain multiple trees. We don\u0027t deal with this problem here. Secondly, the produced dendrograms are fairly messy. Here is an example: \u003cbr\u003e \u003ccenter\u003e \u003cimg src\u003d\"CDN_BASE_URL/217cc00204b8defc34d24cf6b2bfe969?v\u003d1715982720\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e \u003c/center\u003e \u003cbr\u003e Maybe we want to change the order of the objects and have a clean diagram like the one shown above. Your task is to write a program for this purpose, i.e. reordering the objects for a clean diagram. Here, by \u003ci\u003eclean diagrams\u003c/i\u003e, we mean those with no crosses of vertical and horizontal lines. There is usually more than one clean diagram; among them your program should pick the one in which the object of the smaller number comes to the left (in a lexicographical manner). Refer to the sections of Input and Output for the detailed specification. \u003cbr\u003e\u003cdiv align\u003d\"left\" style\u003d\"margin-top: 1.0em;\"\u003e\u003cb\u003eInput\u003c/b\u003e\u003c/div\u003eThe input is given in the following format: \u003cpre\u003e\u003ci\u003eN\u003c/i\u003e \u003ci\u003eM\u003c/i\u003e \u003ci\u003eQ\u003c/i\u003e\n\u003ci\u003esplitInfo\u003c/i\u003e\u003csub\u003e1\u003c/sub\u003e\n\u003ci\u003esplitInfo\u003c/i\u003e\u003csub\u003e2\u003c/sub\u003e\n...\n\u003ci\u003esplitInfo\u003c/i\u003e\u003csub\u003e\u003ci\u003eM\u003c/i\u003e\u003c/sub\u003e\n\u003ci\u003equery\u003c/i\u003e\u003csub\u003e1\u003c/sub\u003e\n\u003ci\u003equery\u003c/i\u003e\u003csub\u003e2\u003c/sub\u003e\n...\n\u003ci\u003equery\u003c/i\u003e\u003csub\u003e\u003ci\u003eQ\u003c/i\u003e\u003c/sub\u003e\n\u003c/pre\u003e The first line contains three integers \u003ci\u003eN\u003c/i\u003e (1 ≤ \u003ci\u003eN\u003c/i\u003e ≤ 100000), \u003ci\u003eM\u003c/i\u003e (0 ≤ \u003ci\u003eM\u003c/i\u003e \u0026lt; \u003ci\u003eN\u003c/i\u003e), and \u003ci\u003eQ\u003c/i\u003e (1 ≤ \u003ci\u003eQ\u003c/i\u003e ≤ 1000, \u003ci\u003eQ\u003c/i\u003e ≤ \u003ci\u003eN\u003c/i\u003e), which represents the numbers of objects, horizontal lines, and queries respectively. Then \u003ci\u003eM\u003c/i\u003e lines follow to describe horizontal lines. Each line is given in the following format: \u003ci\u003eY\u003c/i\u003e \u003ci\u003eL\u003c/i\u003e \u003ci\u003eV\u003c/i\u003e\u003csub\u003e1\u003c/sub\u003e \u003ci\u003eV\u003c/i\u003e\u003csub\u003e2\u003c/sub\u003e... \u003ci\u003eV\u003c/i\u003e\u003csub\u003e\u003ci\u003eL\u003c/i\u003e\u003c/sub\u003e \u003ci\u003eY\u003c/i\u003e (0 ≤ \u003ci\u003eY\u003c/i\u003e ≤ 10\u003csup\u003e9\u003c/sup\u003e) denotes the vertical position of the horizontal line; the smaller value indicates the upper position (or the less similarity). \u003ci\u003eL\u003c/i\u003e is the number of vertical lines (i.e. objects or subgroups of objects) connected by the line. \u003ci\u003eV\u003c/i\u003e\u003csub\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e (for 1 ≤ \u003ci\u003ei\u003c/i\u003e ≤ \u003ci\u003eL\u003c/i\u003e) indicates each of the vertical lines. Each object is indicated by its identifier, a unique number from 1 to \u003ci\u003eN\u003c/i\u003e. Each subgroup of objects is indicated by the identifier of an arbitrary object in the subgroup. Following the description of horizontal lines, there are \u003ci\u003eQ\u003c/i\u003e lines each of which indicates a leaf index at which your program should report which object should be placed. The index is given by a number from 1 (leftmost) to \u003ci\u003eN\u003c/i\u003e (rightmost). \u003cbr\u003e\u003cdiv align\u003d\"left\" style\u003d\"margin-top: 1.0em;\"\u003e\u003cb\u003eOutput\u003c/b\u003e\u003c/div\u003ePrint \u003ci\u003eQ\u003c/i\u003e lines where the \u003ci\u003ei\u003c/i\u003e-th line indicates the identifier of the object at the \u003ci\u003ei\u003c/i\u003e-th queried position. \u003cbr\u003e"}},{"title":"Sample 1","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e3 2 3\n10 2 1 2\n20 2 3 2\n1\n2\n3\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e1\n2\n3\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Sample 2","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e5 2 5\n10 3 1 2 4\n20 3 2 3 5\n1\n2\n3\n4\n5\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e1\n2\n3\n5\n4\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Sample 3","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e4 1 4\n10 2 1 4\n1\n2\n3\n4\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e1\n4\n2\n3\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Sample 4","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e4 3 4\n30 2 1 4\n20 2 2 4\n10 2 3 4\n1\n2\n3\n4\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e1\n4\n2\n3\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Sample 5","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e4 3 4\n10 2 1 4\n20 2 2 4\n30 2 3 4\n1\n2\n3\n4\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e1\n2\n3\n4\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Sample 6","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e4 3 4\n10 2 1 2\n15 2 1 4\n20 2 2 3\n1\n2\n3\n4\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e1\n4\n2\n3\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Sample 7","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e3 2 3\n10 2 2 3\n20 2 1 2\n1\n2\n3\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e1\n2\n3\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Sample 8","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e1 0 1\n1\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e1\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}