eolymp
bolt
Try our new interface for solving problems
Problems

The product of graphs

The product of graphs

Time limit 2 seconds
Memory limit 256 MiB

Given a directed acyclic graph. Standard game on a graph is as follows: initially at one of the vertices of the graph (we call it the starting point) should feature. Two players take turns moving her in the ribs. Plays one who can not make a move.

In game theory is often considered more complex games. For example, the direct product of two games on graphs. The direct product of games - it's the next game: at the beginning of each graph is the starting position on the chip. Over the course of the player moves along the edges of both pieces (each piece moves in its own box). Plays one who can not make a move. That is the one who can not make a move at least one game.

Your task - to determine who will benefit from the proper game.

Input data

The first line will be given numbers N_1 and M_1 - the number of vertices and edges in the first column (1N_1, M_1100000). In the following lines M_1 contains two numbers x and y (1x, yN_1).

The following lines set M_2+1 second graph in the same format.

Ends the input file list of pairs of initial vertices for which you want to solve the problem. On the first line number is set to T (1T100000) - initial number of pairs of vertices. In the following T lines are pairs of vertices v_1 and v_2 (1v_1N_1, 1v_2N_2).

Output data

On each of the pairs of T output the line of initial vertices "first", if correct wins first game, and "second", if the second one.

Examples

Input example #1
3 2
1 2
2 3
2 1
1 2
2
2 1
3 2
Output example #1
first
second