九宫格学校的同学现在正在为吃火锅时什么菜能下什么锅展开激烈讨论。

现在有红汤和清汤两种锅底。有 $n$ 种菜，编号为 $1$ 到 $n$。第 $i$ 种菜在红汤和清汤中煮熟的时间分别为 $a_i,b_i$（保证所有 $a_i$，$b_i$ 均两两不同）。根据讨论结果，他们规定了这些菜能否下在红汤与清汤中。

九宫格学校的同学吃火锅的方式比较特别。他们会先等到所有 $n$ 种菜都上齐，然后决定每种菜要放到红汤锅底中还是清汤锅底中，如果这种菜既可以放在红汤锅底，又可以放在清汤锅底，他们会选择将这种菜放在煮熟时间最短的锅底中。讨论完后，将所有要放到红汤锅底的菜一起全部下入红汤锅，同时将所有要放到清汤锅底的菜一起全部下入清汤锅。由于讨论过程消耗了大量的体力，等到某种菜煮熟时，他们会立刻将这种菜全部捞出并吃掉。

九宫格学校的同学想知道从红汤和清汤中的捞出来的菜分别是什么，请你按捞出时间先后输出答案。

Input

第一行一个整数 $n$（$2\le n \le 10^5$），表示菜的种类数。

接下来 $n$ 行每行四个整数，分别为在红汤中煮熟的时间 $a_i$，在清汤中煮熟的时间 $b_i$，能否煮在红汤中 $c_i$，能否煮在清汤中 $d_i$。其中 $1\le a_i,b_i\le 2\times n$，$c_i,d_i\in \{0,1\}$。保证每个菜至少可以煮在一个锅中，且对于任意 $1\le i,j\le n$，保证 $a_i \neq a_j$，$b_i \neq b_j$ 且 $a_i \neq b_j$。

Output

输出共两行。

第一行先输出一个整数 $k$，表示煮在红汤中的菜数目，接下来 $k$ 个整数，表示红汤中按煮熟时间排序的菜的编号，用空格分隔。

第二行先输出一个整数 $c$，表示煮在清汤中的菜数目，接下来 $c$ 个整数，表示清汤中按煮熟时间排序的菜的编号，用空格分隔。

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

5 4 7 8 3 6
3 2 1 5