Problem Description

There are $N$ bus stops numbered $1, \ldots, N$. Each bus stop $i$ can accommodate $B_{i}$ people.

For each $i \in\{1, \ldots, N-1\}$, there is a pedestrian path connecting bus stop $i$ and bus stop $i+1$, with an open-air market in between. The $i$-th market sells $U_{i}$ umbrellas, each priced at \$1.

Currently, there are $P_{i}$ people in the $i$-th market, and all bus stops are empty.

Suddenly, it starts raining, and everyone in market $i$ must choose one of three options:

• Go to bus stop $i$;
• Go to bus stop $i+1$;
• Stay and buy an umbrella.

If a person cannot find shelter at a bus stop or buy an umbrella, they will get wet.

You need to determine if it is possible to ensure that no one gets wet under the optimal arrangement. If so, you must provide the minimum amount of money spent on umbrellas and the destination bus stop for each person.

Input Format

The first line contains an integer $N$.

The second line contains $N$ space-separated integers $B_{i}\ (1 \leq i \leq N)$, representing the capacity of bus stop $i$.

The third line contains $N-1$ space-separated integers $P_{i}\ (1 \leq i \leq N-1)$, representing the number of people in market $i$.

The fourth line contains $N-1$ space-separated integers $U_{i}\ (1 \leq i \leq N-1)$, representing the number of umbrellas sold in market $i$.

Output Format

If everyone can find shelter under an umbrella or at a bus stop, output $N+1$ lines:

• The first line should be YES.
• The second line should be an integer representing the minimum amount of money spent on umbrellas.
• The next $N-1$ lines should each contain three space-separated integers representing the number of people moving to bus stop $i$, the number of people buying umbrellas in market $i$, and the number of people moving to bus stop $i+1$, respectively.

If there are multiple valid solutions, you may output any one.

Otherwise, output a single line NO.

Sample Input and Output

Input Sample #1

3
10 15 10
20 20
0 0

Output Sample #1

NO

Input Sample #2

3
10 15 10
20 20
0 11

Output Sample #2

YES
5
10 0 10
5 5 10

Notes

Sample 1 Explanation

There are 35 empty spots at the bus stops, and no umbrellas are sold, but there are 40 people in the markets, so the answer is NO.

Sample 2 Explanation

In market $1$, 10 people will go to bus stop $1$, no one will buy an umbrella, and 10 people will go to bus stop $2$.

In market $2$, 5 people will go to bus stop $2$, 5 people will stay and buy an umbrella, and 10 people will move to bus stop $3$.

A total of 5 umbrellas are bought, costing \$5.

Data Range

For all data, $2 \leq N \leq 10^{6}$, $0 \leq B_{i} \leq 2 \cdot 10^{9}$, $0 \leq P_{i},U_{i} \leq 10^{9}$.

见题面 Input 部分

见题面 Output 部分