Trellis Hot Pot School 的学生们正在就哪些食材可以在哪种火锅中烹饪进行激烈的讨论。

火锅分为两种：麻辣火锅和清汤火锅。共有 $n$ 种食材，编号从 $1$ 到 $n$。第 $i$ 种食材在麻辣火锅和清汤火锅中的烹饪时间分别记为 $a_i$ 和 $b_i$（保证所有 $a_i$ 和 $b_i$ 互不相同）。根据讨论结果，他们已经确定了每种食材可以在哪种火锅中烹饪。

Trellis Hot Pot School 的学生们有一种独特的吃火锅方式。他们会等到所有 $n$ 种食材都准备好后，再决定每种食材应该放入麻辣火锅还是清汤火锅。如果一种食材两种火锅都能放，他们会选择将其放入烹饪时间较短的那种火锅中。讨论结束后，所有食材都会被放入相应的火锅中。由于讨论过程非常耗费精力，当某种食材煮熟后，他们会立即将其捞出并食用。

Trellis Hot Pot School 的学生们想知道从麻辣火锅和清汤火锅中捞出食材的顺序。请按捞出时间的先后顺序输出结果。

输入格式

第一行包含一个整数 $n$ ($2 \le n \le 10^5$)，表示食材的种类数。

接下来的 $n$ 行，第 $i$ 行描述第 $i$ 种食材，包含四个整数，分别表示该食材在麻辣火锅中的烹饪时间 $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$。

输出格式

输出两行。

第一行以一个数字 $k$ 开头，表示在麻辣火锅中烹饪的食材数量，随后是 $k$ 个整数，表示麻辣火锅中食材的编号，按烹饪时间排序，以空格分隔。

第二行以一个数字 $c$ 开头，表示在清汤火锅中烹饪的食材数量，随后是 $c$ 个整数，表示清汤火锅中食材的编号，按烹饪时间排序，以空格分隔。

样例

输入 1

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

输出 1

5 4 7 8 3 6
3 2 1 5