Panda 是一名在河上开船的船夫。这艘船一次最多只能搭载一名乘客。

某一天，有 $n$ 个人想要从河的左岸过到右岸。他们到达左岸的时间分别为 $a_1, a_2, \dots, a_n$。还有 $m$ 个人想要从右岸过到左岸。他们到达右岸的时间分别为 $b_1, b_2, \dots, b_m$。乘客只能在他们到达的时间或之后登船。

无论船上是否有乘客，船横渡一次河都需要恰好 $k$ 个单位的时间。Panda 可以选择船的初始位置（左岸或右岸）。目标是找到一个渡河方案，使得所有 $n + m$ 个人中最后一个人到达对岸目的地的时间最早。你还需要帮助 Panda 确定完整的渡河方案。

输入格式

第一行包含三个整数 $n, m, k$ ($1 \le n, m \le 10^5$, $1 \le k \le 10^9$)，分别表示从左岸出发的人数、从右岸出发的人数以及单次渡河所需的时间。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^9$)，表示左岸每个人的到达时间。

第三行包含 $m$ 个整数 $b_1, b_2, \dots, b_m$ ($1 \le b_i \le 10^9$)，表示右岸每个人的到达时间。

输出格式

第一行应包含一个整数 $T$，表示最后一名乘客到达目的地的最早可能时间。

接下来的 $n + m$ 行应按时间顺序描述渡河方案。第 $i$ 行包含三个整数 $t_i, tp_i, id_i$ ($0 \le t_i \le T, tp_i \in \{0, 1\}$)，表示在时间 $t_i$，来自左岸（$tp_i = 0$）或右岸（$tp_i = 1$）且编号为 $id_i$ 的乘客登船。当 $tp_i = 0$ 时，你必须确保 $1 \le id_i \le n$ 且 $t_i \ge a_{id_i}$；当 $tp_i = 1$ 时，你必须确保 $1 \le id_i \le m$ 且 $t_i \ge b_{id_i}$。此外，你必须确保 $t_1 < t_2 < \dots < t_{n+m}$ 且 $T = \max_i(t_i + k)$。

对于一个有效的方案，所有 $n+m$ 个人都必须成功登船并到达对岸。两次连续登船的时间间隔必须至少为 $k$，即对于所有 $1 < i \le n + m$，有 $t_i - t_{i-1} \ge k$。如果连续登船的两个人来自同一侧河岸（$tp_i = tp_{i-1}$），则他们登船的时间间隔必须至少为 $2k$，即 $t_i - t_{i-1} \ge 2k$。

样例

输入样例 1

5 5 2
2 1 13 19 11
12 18 19 7 8

输出样例 1

25
5 0 2
7 1 4
9 0 1
11 1 5
13 0 5
15 1 1
17 0 3
19 1 2
21 0 4
23 1 3