Trace an Array Traversal For Loop

Source: Phước Hưng OJ

Version: Phuoc Hung OJ Extended

Problem Statement

You are given a one-dimensional array of $n$ integers $a_0,a_1,\ldots,a_{n-1}$. Consider a loop that traverses the array in increasing index order. Before the loop, set $S=0$. At iteration $i$, first update $S\leftarrow S+a_i$, then record the triple $(i,a_i,S)$.

Print the complete trace of this loop. The value of $S$ on each line is the prefix sum from $a_0$ through $a_i$.

Input

• The first line contains the integer $n$.
• The second line contains exactly $n$ integers $a_0,a_1,\ldots,a_{n-1}$.

Output

Print exactly $n$ lines. Line $i+1$ contains $i$, $a_i$, and $S_i$, where

Subtasks

Subtask 1 (20 points): $n=1$, $-9\le a_0\le9$.

Subtask 2 (30 points): $2\le n\le20$, $0\le a_i\le10^4$.

Subtask 3 (50 points): $1\le n\le1000$, $-10^9\le a_i\le10^9$.

Examples

Input

5
4 -2 7 0 3

Output

0 4 4
1 -2 2
2 7 9
3 0 9
4 3 12

Explanation

Initially $S=0$.

• For $i=0$, $a_0=4$, so $S=4$.
• For $i=1$, $a_1=-2$, so $S=2$.
• For $i=2$, $a_2=7$, so $S=9$.
• For $i=3$, $a_3=0$, so $S$ remains $9$.
• For $i=4$, $a_4=3$, so $S=12$.

Each line reports the current index, the current element, and the updated sum.