CF254E.Dormitory

Student Vasya came to study in Berland State University from the country, so he is living in a dormitory. A semester has n days, and in each of those days his parents send him some food. In the morning of the i-th day he receives a__i kilograms of food that can be eaten on that day and on the next one (then the food goes bad and becomes unfit for consumption).

Every day Vasya eats v kilograms of food. It is known that Vasya's parents do not allow him to starve, so there always is enough food for Vasya. Vasya has m friends who sometimes live with him. Let's index the friends from 1 to m. Friend number j lives with Vasya from day l__j to day r__j, inclusive. Also, the j-th friend requires f__j kilograms of food per day. Usually Vasya's friends eat in the canteen, but sometimes generous Vasya feeds some of them. Every day Vasya can feed some friends who live with him this day (or may feed nobody).

Every time Vasya feeds his friend, he gives him as much food as the friend needs for the day, and Vasya's popularity rating at the University increases by one. Vasya cannot feed the same friend multiple times in one day. In addition, he knows that eating habits must be regular, so he always eats v kilograms of food per day.

Vasya wants so choose whom he will feed each day of the semester to make his rating as high as possible. Originally Vasya's rating is 0 because he is a freshman.

学生瓦夏从国外来到贝尔兰国立大学学习，因此他住在宿舍里。一个学期共有 $n$ 天，每天他的父母都会给他寄送一些食物。在第 $i$ 天清晨，他收到 $a_i$ 千克的食物，这些食物可在当天及次日食用（之后便会变质，无法再食用）。

瓦夏每天需食用 $v$ 千克食物。已知瓦夏的父母不允许他挨饿，因此总能保证他拥有充足的食物。瓦夏有 $m$ 位朋友偶尔会与他同住。我们将这些朋友编号为 $1$ 至 $m$。第 $j$ 位朋友在第 $l_j$ 天至第 $r_j$ 天（含端点）期间与瓦夏同住。此外，第 $j$ 位朋友每天需要 $f_j$ 千克食物。通常情况下，瓦夏的朋友们都在食堂就餐，但有时慷慨的瓦夏会为其中部分朋友提供食物。每天，瓦夏可选择为当日与他同住的部分朋友提供食物（也可不提供任何朋友）。

每当瓦夏为某位朋友提供食物时，他都会给予该朋友当天所需的全部食物量，同时他在大学的“人气评分”将增加 1 分。瓦夏不能在同一天内多次为同一位朋友提供食物。此外，他还深知饮食习惯须规律，因此他每天都严格食用 $v$ 千克食物。

瓦夏希望在学期的每一天中，恰当地选择为哪些朋友提供食物，以使他的人气评分最大化。初始时，瓦夏的人气评分为 0（因为他是一名新生）。

The first line contains two integers n and v (1 ≤ n, v ≤ 400). The second line contains n integers _a_1, _a_2, ..., a__n (1 ≤ a__i ≤ 400), separated by single spaces. Value a__i means that in the morning of the i-th day a__i kilograms of food come, the food is good for eating on day i and/or on day i + 1 (then the food goes bad). It is guaranteed that if Vasya doesn't feed anyone, there is a way for him to eat so as to consume v kilograms of food every day.

The third line contains integer m (1 ≤ m ≤ 400). Each of the following m lines describes one Vasya's friend: the j-th of these lines contains three integers l__j, r__j, f__j (1 ≤ l__j ≤ r__j ≤ n, 1 ≤ f__j ≤ 400), separated by single spaces.

第一行包含两个整数 $n$ 和 $v$（$1 \leq n, v \leq 400$）。
第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \leq a_i \leq 400$），以单个空格分隔。数值 $a_i$ 表示在第 $i$ 天早晨送达 $a_i$ 千克食物，该食物仅可在第 $i$ 天和/或第 $i+1$ 天食用（之后变质）。题目保证：若 Vasya 不喂养任何人，则存在一种进食方案，使得他每天恰好消耗 $v$ 千克食物。

第三行包含一个整数 $m$（$1 \leq m \leq 400$）。接下来的 $m$ 行每行描述一位 Vasya 的朋友：其中第 $j$ 行包含三个整数 $l_j, r_j, f_j$（$1 \leq l_j \leq r_j \leq n$, $1 \leq f_j \leq 400$），以单个空格分隔。

In the first line print the highest rating Vasya can reach. In the next n lines print, which friends Vasya needs to feed on each day. In the i-th of these lines first print the number of friends to feed on the i-th day, and then list the indexes of these friends. Print the friends in these lists in any order. If there are multiple optimal solutions, print any of them.

第一行输出 Vasya 能达到的最高评分。接下来的 $n$ 行中，每行输出第 $i$ 天 Vasya 需要喂食的朋友列表。在这些行中的第 $i$ 行，首先输出第 $i$ 天需要喂食的朋友人数，然后列出这些朋友的编号（索引）。这些列表中的朋友顺序可以任意。如果存在多个最优解，输出其中任意一个即可。