G. Beyond the Stars
time limit per test
8 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

This is a communication problem. Pay attention to its unusual constraints.

That was long ago, in a past forgotten by all of ECUST...

In that forgotten age, Zhulin and Qianwai fought side by side, lived together, and gazed up at the same stars. Later, sand buried their language, oceans severed their roads, and even their names faded from history. Only the vast, silent star chart above them remained: public, radiant, and unchanging. Yet nobody knew which stars they had once quietly joined into a message.

This problem has $$$20$$$ test cases.

You are given an undirected graph $$$G=(V,E)$$$ with $$$|V|=2000$$$ and $$$|E|=43\,600$$$. It has no multiple edges or self-loops and is generated as follows. Initially, $$$G$$$ has $$$|V|$$$ vertices and no edges. Then, $$$|E|$$$ times, the generator uniformly chooses one of the vertex pairs not yet joined by an edge and adds an undirected edge between them.

Your program will be run twice:

First run

In the first run, you play Zhulin. Choose and output $$$n$$$ induced four-cycles in $$$G$$$. They may share vertices.

  • Definition of an induced four-cycle: Choose $$$4$$$ vertices of $$$G$$$ that have exactly $$$4$$$ edges among them, forming a simple cycle. In particular, there are no diagonals.

Second run

In the second run, you play Qianwai. The judge has your complete output from the first run. For each of $$$q$$$ queries, it selects one of your four-cycles, deletes one of its vertices, and gives you the other three vertex numbers. Report the index of the four-cycle in Zhulin's output from which they came.

Input

First run

The first line contains the string send.

The second line contains an integer $$$n$$$ ($$$n=200\,000$$$), the number of induced four-cycles you must output.

The third line contains two integers $$$|V|$$$ and $$$|E|$$$.

Each of the next $$$|E|$$$ lines contains two integers $$$u,v$$$, indicating an undirected edge between vertices $$$u$$$ and $$$v$$$ ($$$1 \le u,v \le |V|$$$).

Second run

The first line contains the string receive.

The second line contains two integers $$$|V|$$$ and $$$|E|$$$.

Each of the next $$$|E|$$$ lines contains two integers $$$u,v$$$, indicating an undirected edge between vertices $$$u$$$ and $$$v$$$ ($$$1 \le u,v \le |V|$$$).

Line $$$|E|+3$$$ contains an integer $$$q$$$ ($$$q=4n$$$), the number of received vertex sets.

Each of the next $$$q$$$ lines contains $$$3$$$ integers: the vertices remaining after the judge removes one vertex from a four-cycle in your first-run output.

Output

First run

Output $$$n$$$ lines. Line $$$i$$$ contains four integers $$$v_1,v_2,v_3,v_4$$$, the vertices of the $$$i$$$-th induced four-cycle.

Second run

Output $$$q$$$ lines. For each received vertex set, output an integer $$$i$$$ ($$$1 \le i \le n$$$), the index of its four-cycle.

Examples
Input
send
200000
2000 43600
29 1973
228 1127
...
92 573
Output
1 174 613 1323
1 955 1683 1755
...
1390 1615 1683 1777
Input
receive
2000 43600
29 1973
228 1127
...
92 573
800000
46 1297 1949
1056 1275 1454
...
387 1289 1533
Output
17713
191947
...
118231
Note

Parts of the sample are omitted because the complete data is too large.