L. Beef Tripe in Soup Pot?
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Students at the Trellis Hot Pot School are currently engaged in a heated discussion about which ingredients can be cooked in which type of hot pot.

There are two types of hot pots: spicy hot pots and soup pots. There are $$$n$$$ types of ingredients, numbered from $$$1$$$ to $$$n$$$. The cooking times for the $$$i$$$-th ingredient in the spicy hot pot and soup pot are denoted as $$$a_i$$$ and $$$b_i$$$, respectively (it is guaranteed that all $$$a_i$$$ and $$$b_i$$$ are distinct). Based on the discussion results, they have determined which ingredients can be cooked in each type of hot pot.

The students at the Trellis Hot Pot School have a unique way of eating hot pots. They will wait until all $$$n$$$ types of ingredients are ready and then decide whether each ingredient should be placed in the spicy hot pot or soup pot. If an ingredient can be placed in both pots, they will choose to place it in the pot with the shorter cooking time. After the discussion, all ingredients are put into the regarding pot. Due to the exhausting discussion process, when an ingredient is cooked, they will immediately fish it out and eat it.

The students at the Trellis Hot Pot School want to know the order in which the ingredients are fished out from the spicy hot pot and soup pot, respectively. Please output the answers in the order of fishing out time.

Input

The first line contains an integer $$$n$$$ ($$$2\le n \le 10^5$$$), indicating the number of types of ingredients.

For the next $$$n$$$ lines, the $$$i$$$-th line describes the $$$i$$$-th type of ingredients, which contains four integers representing the cooking time $$$a_i$$$ in the spicy hot pot, cooking time $$$b_i$$$ in the soup pot, whether the ingredient can be cooked in the spicy hot pot $$$c_i$$$, and whether the ingredient can be cooked in the soup pot $$$d_i$$$. Here, $$$1\le a_i,b_i\le 2\times n$$$, $$$c_i,d_i\in \{0,1\}$$$. It is guaranteed that each ingredient can be cooked in at least one type of hotpot, and for any $$$1\le i,j\le n$$$, it is guaranteed that $$$a_i \neq a_j$$$, $$$b_i \neq b_j$$$, and $$$a_i \neq b_j$$$.

Output

Output two lines.

The first line should start with a number $$$k$$$, representing the number of ingredients cooked in the spicy hot pot, followed by $$$k$$$ integers representing the type of the ingredients in the spicy hot pot, sorted by cooking time, separated by spaces.

The second line should start with a number $$$c$$$, representing the number of ingredients cooked in the soup pot, followed by $$$c$$$ integers representing the type of the ingredients in the soup pot, sorted by cooking time, separated by spaces.

Example
Input
8
9 11 0 1
1 8 0 1
15 7 1 0
3 13 1 1
6 12 0 1
16 5 1 0
4 2 1 0
10 14 1 0
Output
5 4 7 8 3 6
3 2 1 5