G. Utakotoba
time limit per test
1 second
memory limit per test
512 megabytes
input
standard input
output
standard output

After playing Haruhikage, MyGO has broken, and all words are powerless to it now. However, as Uika has said, more than words, the feeling gets through. So Tomori decides to sing out whatever comes from her heart on the stage to appeal to her band. To save her band, Tomori needs to transform the current emotion sequence of the band to a specific resonating one.

The initial sequence $$$A$$$ consists of $$$n$$$ non-negative integers, indexed from 1. Each line of the lyrics of Tomori's song will have an impact $$$op(x,y)$$$ on the current sequence $$$A$$$, replacing $$$A_x$$$ with $$$(A_x\ \text{XOR}\ A_y)$$$ while $$$1\leq x,y\leq n$$$, and $$$|x-y|=1$$$.

You are given the initial sequence $$$A$$$ and the resonating sequence $$$B$$$, and you should provide a possible version of the impacts of Tomori's song, which transforms $$$A$$$ to $$$B$$$.

Note that, as Tomori is just a vulnerable girl (unlike Kokoro) and cannot stay too long on the stage, the number of lines of the song's lyrics has to be no more than $$$150\times n$$$ .

(see input/output format for more details)

Input

The first line contains a single integer $$$n$$$ ($$$1\leq n \leq 2\times 10^4$$$) representing the number of elements of the sequence.

The following line contains $$$n$$$ integers separated with spaces, and the $$$i$$$-th integer represents the value of $$$A_i$$$ $$$(0\leq A_i \lt 2^{15})$$$.

The next line also contains $$$n$$$ integers separated with spaces, and the $$$i$$$-th integer represents the value of $$$B_i$$$ $$$(0\leq B_i \lt 2^{15})$$$.

It is guaranteed that, for every given input, at least one answer exists.

Output

You should first output a single line of a non-negative integer $$$m$$$, representing the number of the impacts of your version of the song, and $$$m$$$ should be no more than $$$150\times n$$$ .

Then you should output $$$m$$$ lines, each of which contains two integers $$$x,y$$$ ($$$1\leq x,y\leq n, |x-y|=1$$$), and the $$$x,y$$$ in the $$$i$$$-th line means the $$$i$$$-th impact of your version of the song is $$$op(x,y)$$$.

If there are multiple possible answers, just output any one of them.

Example
Input
5
2 2 6 6 6
4 6 0 0 2
Output
10
2 3
3 2
4 3
5 4
4 3
3 2
4 3
2 1
3 2
1 2