E. Esoteric Computer Architecture 2
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

During the Segunda Fecha del Gran Premio de México, Ángel built his unusual computer prototype. Thanks to your help, he was able to complete his assignment, but a new defect has now appeared.

This time, the problem lies in the rotation instruction. Ángel wants to transform an array $$$A = [a_1, a_2, \dots, a_n]$$$ into another array $$$B = [b_1, b_2, \dots, b_n]$$$. He can perform the following operation any number of times:

  • Choose indices $$$l,r$$$ with $$$1 \le l \le r \le n$$$, and an integer $$$k$$$ with $$$0 \leq k \leq 10^6$$$. Rotate the subarray $$$A[l,r]$$$ to the left at the digit level exactly $$$k$$$ times.

For example, if $$$A = [12, 345, 67, 8, 9]$$$ and you apply the operation on the subarray $$$A[2,4]$$$ with $$$k=2$$$, the result is $$$[12, 567, 83, 4, 9]$$$.

Decide whether it is possible to transform $$$A$$$ into $$$B$$$ using a sequence of such operations. If it is possible, you must also output one valid sequence.

Input

The file contains multiple test cases. The first line contains an integer $$$t$$$ $$$(1 \leq t \leq 5 \cdot 10^4)$$$ — the number of test cases.

The first line of each test case contains an integer $$$n$$$ ($$$1 \leq n \leq 5 \cdot 10^4$$$) — the size of the arrays $$$A$$$ and $$$B$$$.

The second line of each test case contains $$$n$$$ integers $$$A_1,A_2,\dots,A_n$$$ ($$$1 \leq A_i \lt 10^4$$$) — the array $$$A$$$.

The third lin of each test casee contains $$$n$$$ integers $$$B_1,B_2,\dots,B_n$$$ ($$$1 \leq B_i \lt 10^4$$$) — the array $$$B$$$.

It is guaranteed that no element of the arrays contains the digit $$$0$$$.

It is guaranteed that the sum of all values of $$$n$$$ over the input does not exceed $$$5 \cdot 10^4$$$.

Output

For each test case, print an integer $$$m$$$ ($$$0 \leq m \leq 16n$$$) in the first line of your output if it is possible to transform array $$$A$$$ in array $$$B$$$; otherwise print $$$-1$$$.

If it is possible, then print $$$m$$$ lines with the operations. Each operation should be indicated with three integers $$$l$$$, $$$r$$$, and $$$k$$$ ($$$1 \leq l \leq r \leq n$$$ and $$$0 \leq k \leq 10^6$$$) — the parameters of each operation.

Example
Input
1
4
123 45 6 78
345 26 7 81
Output
2
1 2 2
2 4 1