Ms. Wozzie has a variable-length array $$$S$$$. Initially $$$S$$$ is empty, and the array will be manipulated $$$N$$$ times, each time adding a number to the end of $$$S$$$.
She wants to check the current state of the array when she adds the $$$i$$$-th number $$$S_i$$$, so she will give you a pair of $$$A_i,B_i$$$ at the same time, and wants you to output the current value of $$$\sum_{i=1}^{n} \sum_{j=i}^{i+z_i-1} A_j \times B_i$$$. Define $$$z_i$$$ as the longest common prefix of $$$[S_i ,\dots ,S_n]$$$ and $$$[S_1,\dots,S_n]$$$ where $$$n$$$ is the current length.
Recall that the longest common prefix of $$$[a_1,\dots, a_n]$$$ and $$$[b_1, \dots, b_m]$$$ is the largest $$$L$$$ satisfying: $$$a_i = b_i, \forall 1 \leq i \leq L$$$.
To make sure you answered her question in real time, she will encrypt the number $$$S_i$$$ she is currently adding backward through your last answer, the exact decryption is given in the input format.
The first line contains an integer $$$N$$$ ($$$2 \leq N \leq 3 \times 10^5$$$) indicating the number of operations.
For the next $$$N$$$ lines, the $$$i$$$-th line contains three integers $$$S_i',A_i,B_i$$$ ($$$0 \leq S_i' \lt N, 1 \leq A_i, B_i \leq 1000$$$) representing the encrypted $$$S_i$$$ and $$$A_i, B_i$$$.
For decryption: the value of $$$S_i$$$ is $$$(S_i' + lastans) \mod N$$$, where $$$lastans$$$ denotes the last output answer. In particular, initially, $$$lastans = 0$$$.
Output $$$N$$$ lines, with the $$$i$$$th line representing the answer after the $$$i$$$-th operations on $$$S$$$.
30 1 21 2 32 3 4
2 12 18
