33076번 - 조명

문제

수학토끼는 $xy$평면에 살고 있는 서울과학고 학생이다. 편의상 $x$가 증가하는 방향을 오른쪽, $y$가 증가하는 방향을 위쪽이라고 하자. 암흑 공포증이 있는 수학토끼는 도로를 이동하며 조명을 켜고 있어야만 한다. 구체적으로, 조명의 위치는 다음과 같은 규칙을 따른다.

• 수학토끼와 조명은 $xy$평면에 있는 점으로 가정한다.
• 수학토끼의 위치는 도로에 있는 점이며, 수학토끼로부터 연직 위로 $y(\ge 0)$만큼 떨어진 지점에 조명이 있다.
• 이 조명은 아래 방향으로 빛을 내며, 연직 아래를 기준으로 좌우 최대 45ドル$도까지 빛을 낸다.
• 빛은 조명에서 출발하여 도로에 평행하지 않게 입사할 때까지 반직선 형태로 이동한다고 가정한다.
• 수학토끼는 조명의 높이 $y$를 조명이 비추는 영역의 $x$좌표의 최솟값과 최댓값의 차이가 $D$ 이상이 되는 최소 높이로 설정한다. 이때, $D$는 고정된 짝수인 양의 정수다.

$N(\ge 2)$개의 짝수인 양의 정수 $a_1, a_2, \cdots, a_N$이 주어질 때 수학토끼가 걸어갈 도로는 다음과 같이 생겼다.

• $(0, 0)$에서 시작하여 오른쪽으로 기울기 1ドル,ドル 길이 $\sqrt{2}a_1$인 선분 형태의 도로가 있다. 이를 1ドル$번째 도로라고 한다.
• $i-1$번째 도로의 오른쪽 끝점에서 시작하여 오른쪽으로 기울기 $(-1)^{i-1},ドル 길이 $\sqrt{2} a_i$인 선분 형태의 도로가 있다. 이를 $i$번째 도로라고 한다. $(2 \le i \le N)$
• 1ドル$번째 도로의 기울기와 $N$번째 도로의 기울기는 각각 1ドル,ドル $-1$임이 보장된다. 즉, $N$은 짝수이다.
• 1ドル$번째 도로의 왼쪽 끝점에서 시작하여 왼쪽으로 기울기 $-1$의 반직선 형태의 도로가 있다.
• $N$번째 도로의 오른쪽 끝점에서 시작하여 오른쪽으로 기울기 1ドル$의 반직선 형태의 도로가 있다.

예제 1의 도로 형태

수학토끼의 위치에 따라 조명이 도로 위에 놓일 수도 있음에 유의하자. 예를 들어, 위의 그림에 그려진 예제 1의 경우, 수학토끼가 $x=2$에 있는 경우 조명은 $(2, 2)$ 지점에 놓이고, 이때 조명이 비추는 부분은 0ドル \le x \le 6$이다(예제 설명 참고).

수학토끼는 $x=0$에서 시작하여 오른쪽으로 도로를 따라 $x=\sum_{i=1}^N a_i$까지 이동한다. 이때, 조명의 자취는 유한 개의 선분의 합집합으로 표현 가능한 연결된 곡선을 이룬다. 조명의 자취를 최소 개수의 선분으로 표현하는 프로그램을 작성하여라.

입력

첫 번째 줄에 $N,ドル $D$가 공백으로 구분되어 주어진다.

두 번째 줄에 $N$개의 양의 정수 $a_1, a_2, \cdots, a_N$이 공백으로 구분되어 주어진다.

출력

첫 번째 줄에 조명의 자취를 표현하기 위한 선분의 최소 개수를 출력한다.

두 번째 줄부터 한 줄에 선분 한 개씩 $a_i$ $b_i$ $c_i$ $d_i$ 형태로 출력한다. $i$번째 선분은 $(a_i, b_i)$와 $(c_i, d_i)$를 연결하는 선분이라는 뜻이다. $a_i \le c_i$를 만족해야 하며, $a_1 \le a_2 \le \cdots$를 만족해야 한다. 이러한 출력은 유일하며, 모든 값이 정수임을 증명할 수 있다.

제한

• 2ドル \le N \le 2 \times 10^5$
• 2ドル \le D \le \sum_{i=1}^N a_i$
• 2ドル \le a_i \le 10^9$ $(1 \le i \le N)$
• $N,ドル $D,ドル $a_i$는 짝수 $(1 \le i \le N)$

힌트