E. XOR Sorting
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a list of $$$n$$$ integers from $$$0$$$ to $$$2^{20}-1$$$.

The following operation can be performed any number of times (zero or more).

Choose two distinct positions $$$1 \le x,y \le n$$$ and assign: $$$$$$a_x := a_x \, \mathsf{XOR} \, a_y$$$$$$ Where $$$\mathsf{XOR}$$$ is the bitwise XOR of the two numbers.

You need to perform these operations so that the resulting list is sorted in non-decreasing order (i.e., $$$a_i \le a_{i+1}$$$ for each position $$$i$$$ from $$$1$$$ to $$$n-1$$$).

Can you construct a sufficiently short sequence of operations to solve this task?

Input

The first line contains the number $$$n$$$, the size of the list.

The second line contains $$$n$$$ integers $$$a_1, \ldots, a_n$$$.

Output

On the first line, print the number of operations $$$m$$$.

On the following $$$m$$$ lines, print the positions $$$x$$$ and $$$y$$$.

Scoring
  1. (100 points) No additional restrictions.

Additionally, the score you get depends on the number of operations you perform: to get a full score you must perform at most $$$2500$$$ operations and to get a positive score you must perform at most $$$21000$$$ operations. The score for each subtask is multiplied by a multiplier $$$M(m)$$$, where $$$m$$$ is the maximum number of operations you have performed in the cases of that subtask. The value of $$$M(m)$$$ is given by:

$$$$$$ M(m) = \begin{cases} 0 & m \gt 21000 \\ 0.1 + \frac{21000-m}{90000} & 21000 \geq m \gt 3000 \\ 0.3 + \frac{21000-7m}{5000} & 3000 \geq m \gt 2500 \\ 1.0 & 2500 \geq m \end{cases} $$$$$$

Examples
Input
5
0 1 1 1 2
Output
0
Input
5
4 3 2 1 0
Output
5
5 1
1 5
2 3
2 4
4 3
Note

$$$n = 1000$$$ in all cases.

The examples show cases with $$$n \lt 1000$$$ only to help you. They will not appear in the actual test cases.

$$$0 \le a_i \le 2^{20}-1$$$.

You can perform at most $$$21000$$$ operations.