Ms. Wozzie 有一个变长数组 $S$。初始时 $S$ 为空，该数组将被操作 $N$ 次，每次在 $S$ 的末尾添加一个数字。

她希望在添加第 $i$ 个数字 $S_i$ 时检查数组的当前状态，因此她会同时给你一对 $A_i, B_i$，并要求你输出当前值 $\sum_{i=1}^{n} \sum_{j=i}^{i+z_i-1} A_j \times B_i$。

定义 $z_i$ 为 $[S_i, \dots, S_n]$ 和 $[S_1, \dots, S_n]$ 的最长公共前缀，其中 $n$ 是当前数组的长度。

回想一下，$[a_1, \dots, a_n]$ 和 $[b_1, \dots, b_m]$ 的最长公共前缀是满足 $a_i = b_i, \forall 1 \le i \le L$ 的最大 $L$。

为了确保你能实时回答她的问题，她会将当前添加的数字 $S_i$ 通过你上一次的答案进行加密，具体的解密方式在输入格式中给出。

输入格式

第一行包含一个整数 $N$ ($2 \le N \le 3 \times 10^5$)，表示操作次数。

接下来的 $N$ 行中，第 $i$ 行包含三个整数 $S'_i, A_i, B_i$ ($0 \le S'_i < N, 1 \le A_i, B_i \le 1000$)，分别表示加密后的 $S_i$ 以及 $A_i, B_i$。

解密方式：$S_i$ 的值为 $(S'_i + lastans) \pmod N$，其中 $lastans$ 表示上一次的输出答案。特别地，初始时 $lastans = 0$。

输出格式

输出 $N$ 行，第 $i$ 行表示在 $S$ 上进行第 $i$ 次操作后的答案。

样例

输入 1

3
0 1 2
1 2 3
2 3 4

输出 1

2
12
18