CF1776D.Teamwork

As soon as SWERC starts, your experienced $3$-person team immediately realizes that the contest features $a$ easy problems, $b$ medium problems, and $c$ hard problems. Solving a problem will take any of you $2$, $3$, or $4$ time units, depending on whether the problem is easy, medium, or hard. Regardless of the difficulty of the problem, the last time unit spent to solve it has to be spent using your shared computer.

You organize your efforts so that each of you starts (and ends) solving problems at integer time units. Any given problem can be solved by only one contestant; it requires a contiguous amount of time (which depends on the difficulty of the problem). None of the $3$ of you can solve more than one problem at a time, but you can start solving a new problem immediately after finishing one. Similarly, the shared computer cannot be used by more than one of you at a time, but any of you can start using the computer (to complete the problem currently being solved) immediately after someone else stops using it.

Given that the contest lasts $l$ time units, find the maximum number of problems that your team can solve. Additionally, find one way to solve the maximum number of problems.

SWERC 开始后，你们这支经验丰富的三人队伍立即发现本次比赛共有 $a$ 道简单题、$b$ 道中等题和 $c$ 道难题。解决一道题目所需时间为 $2$、$3$ 或 $4$ 个时间单位，分别对应题目难度为简单、中等或困难。无论题目难度如何，解决该题的最后一个时间单位必须使用你们共用的计算机。

你们协调分工，使得每位队员均在整数时刻开始（并结束）解题。任意一道题目只能由一名队员独立完成，且需连续占用相应时长（取决于题目难度）。三人中任意一人同一时刻最多只能解一道题，但可在刚完成一道题后立即开始下一道题。类似地，共用计算机同一时刻最多只能被一人使用，但当某位队员刚释放计算机后，其他任意队员可立即使用它（以完成当前正在解的题目）。

已知比赛总时长为 $l$ 个时间单位，求你们队伍最多能解决多少道题目；并给出一种达成该最大题数的具体方案。

The input has a single line. It contains four integers $a$, $b$, $c$, $l$ ($0 \leq a, b, c, \leq 10^4$, $0 \le l \le 10^5$) — the number of easy, medium, and hard problems, and the duration of the contest.

输入仅有一行。包含四个整数 $a$、$b$、$c$、$l$（$0 \leq a, b, c \leq 10^4$，$0 \le l \le 10^5$）——分别表示简单题、中等题和难题的数量，以及比赛的持续时间。

On the first line, print a single integer $n$ — the maximum number of problems that your team can solve.

Then, on the $j$-th of the following $n$ lines, print three integers $x_j$, $p_j$, $q_j$ ($1 \leq x \leq 3$, $0 \leq p_j \lt q_j \leq l$) — the contestant that solves the $j$-th problem, and the start and end time for solving the $j$-th problem (measured as time units elapsed from the beginning of the contest). The difference $q_j - p_j$ is $2$, $3$, or $4$, depending on the difficulty of the problem.

The last $n$ lines are to be provided in increasing order of end time: $q_1 \lt q_2 \lt \cdots \lt q_n$. If there are multiple ways to solve $n$ problems, output any of them.

第一行输出一个整数 $n$ —— 你的队伍最多能解决的问题数量。

接下来的 $n$ 行中，第 $j$ 行输出三个整数 $x_j$、$p_j$、$q_j$（其中 $1 \leq x \leq 3$，$0 \leq p_j \lt q_j \leq l$）—— 分别表示解决第 $j$ 个问题的参赛队员，以及解决该问题的起始时间和结束时间（以比赛开始后经过的时间单位计量）。差值 $q_j - p_j$ 为 $2$、$3$ 或 $4$，具体取决于该问题的难度。

最后这 $n$ 行需按结束时间递增顺序给出：即满足 $q_1 \lt q_2 \lt \cdots \lt q_n$。若存在多种解决 $n$ 个问题的方式，输出任意一种即可。

In the first sample, the first contestant solves an easy problem between time $0$ and time $2$ while the second contestant solves a medium problem between time $0$ and time $3$.

In the second sample, the first contestant solves an easy problem between time $0$ and time $2$, and then also solves a medium problem between time $2$ and time $5$. In the meantime, the second contestant solves another medium problem between time $0$ and time $3$, while the third contestant solves a hard problem between time $0$ and time $4$.

In the third sample, the contest only has medium and hard problems, and there is not enough time to solve any of them.

在第一个样例中，第一位参赛者在时间 $0$ 到 $2$ 之间解决了一道简单题，而第二位参赛者在时间 $0$ 到 $3$ 之间解决了一道中等题。

在第二个样例中，第一位参赛者在时间 $0$ 到 $2$ 之间解决了一道简单题，随后又在时间 $2$ 到 $5$ 之间解决了一道中等题。与此同时，第二位参赛者在时间 $0$ 到 $3$ 之间解决了另一道中等题，而第三位参赛者在时间 $0$ 到 $4$ 之间解决了一道难题。

在第三个样例中，比赛仅包含中等题和难题，且时间不足以解决其中任意一道。