<table border=0>
<tr>
<td width="80%">
EJOI 2020 Day 2 </br>
<b>xorsort</b> (Slovene)
</td>
<td width="20%">
<img align="right" width="100" src="https://i.imgur.com/KUVHoM0.png">
</td>
</tr>
</table>

# XOR_Urejanje

## Naloga

Dana sta celo število $S$ in polje $\mathbf{A}$, ki hrani $N$ nenegativnih celih števil, oštevilčenih od 1 naprej.
Na elementih polja $\mathbf{A}$ so dovoljene naslednje operacije:
Za poljuben indeks $i$, $(1 \le i \le N)$ izberete enega od sosedov elementa $A_i$, to je element $A_j$, kjer je $j = i - 1$ oziroma $j = i + 1$ in ga nadomestite z $(A_i \oplus A_j)$, kjer je $\oplus$ bitna operacija XOR, ki je definirana na koncu besedila.
Vaša naloga je spremeniti polje $\mathbf{A}$ v urejeno polje:

* Če je $S=1$ mora biti rezultirajoče polje strogo naraščajoče, $A_i < A_{i+1}$, za $1 \le i < N$.
* Če je $S=2$ mora biti rezultirajoče polje nepadajoče, $A_i \le A_{i+1}$, za $1 \leq i < N$.

Poiščte katerokoli zaporedje operacij, ki vas pripelje do rezultata.
Ni potrebno optimirati števila operacij. Pomembno je le, da število operacij ne presega $40000$.

## Vhod

V prvi vrstici vhoda se nahajata dve celi števili $N$ in $S$.
V naslednji vrstici se nahaja $N$ celih števil: $A_1$ $A_2$ ... $A_N$, ki so elementi polja $\mathbf{A}$.

## Izhod

Prva vrstica vsebuje celo število $K$, $(0 \leq K \leq 40000)$, ki predstavlja število operacij.

V naslednjih $K$ vrsticah sta zapisani po dve celi števili, ki povesta, kako so potekale operacije v časovnem zaporedju: prvo število je indeks $i$ elementa, ki je bil nadomeščen, drugo število, pa je indeks $j$ elementa, ki je sodeloval v operaciji.

## Omejitve

* $1 \leq S \leq 2$
* $2 \leq N \leq 1000$
* $0 \leq A_i \leq 2^{20}$

## Podnaloge

1. podnaloga (25 točk): $2\leq N \leq 150$, $S=1$ in vsi elementi $A_i$ so različni.
2. podnaloga (35 točk): $2 \leq N \leq 200$, $S=1$ in vsi elementi $A_i$ so različni.
3. podnaloga (40 točk): $2 \leq N \leq 1000$ in $S=2$.

## Primeri

### 1. primer

#### Vhod

5 1 
3 2 8 4 1

#### Izhod

3
1 2
4 3
5 4

### 2. primer

#### Vhod

5 2
4 4 2 0 1

#### Izhod

3
3 2
4 3
5 4

### Komentar

V prvem primeru smo naredili naslednje operacije na elementih polja:
$[3, 2, 8, 4, 1] \rightarrow [\mathbf{1}, 2, 8, 4, 1] \rightarrow [1, 2, 8, \mathbf{12}, 1] \rightarrow [1, 2, 8, 12, \mathbf{13}]$,

medtem, ko smo v drugem primeru naredili naslednje operacije:
$[4, 4, 2, 0, 1] \rightarrow [4, 4, \mathbf{6}, 0, 1] \rightarrow [4, 4, 6, \mathbf{6}, 1] \rightarrow [4, 4, 6, 6, \mathbf{7}]$.

Rezultat operacije XOR na bitih $a$ in $b$ je enak 0
če je $a=b$, sicer pa je rezultat enak 1.

Operacija XOR na celih številih se izvede na istoležnih bitih v binarnem zapisu števil.

Na primer
$75 \oplus 29 = 86$
$1001011 \oplus 0011101 = 1010110$

V C/C++ in Javi lahko uporabite implementirano operacijo XOR, ki se označi z znakom `^`.