小青鱼来到了重（zhòng）庆市的一个迷宫，名为比特迷宫。听说只有最聪明的人才能从里面走出。

这个迷宫看似容易，但在小青鱼即将走出迷宫的时候，却被 $n=2^k$ 个比特机器人拦住了去路。这些机器人从左到右显示着 $a_0,a_1,\cdots ,a_{n-1}$，表示一个 $n-1$ 次的多项式 $P(x)=a_0+a_{1}x+\cdots +a_{n-1}{x}^{n-1}$ 的系数。比特机器人喜欢比特，所以每个系数只可能是 0 或者 1。

小青鱼是无法单独修改某一个比特机器人显示的系数的，但是这个迷宫提供了一个批量修改的操作：输入两个非负整数 $a,b$ ($a+b\le n-1$)，显示第 $i$ 次项系数的比特机器人会算出 $x^a(1+x{)}^b$ 的第 $i$ 次项系数 $c_i$，然后将自己显示的值 $a_i$ 修改为 $(a_i+c_i)mod2$，其中 $mod2$ 表示对 $2$ 取模。

整体来看，这个操作的作用是将这个多项式 $P(x)$ 在 $mod2$ 意义上加上 $x^a(1+x{)}^b$。

由于这个迷宫是困难模式，小青鱼只能操作不超过 $T$ 次。当多项式变为 $0$ 的时候，也即所有比特机器人都显示 $0$ 的时候，他就通关了。

小青鱼左思右想没有想到通关的方式，于是他找到了你来帮忙。

输入格式

第一行，三个整数 $n,k,T$。保证 $n=2^k$。

第二行 $n$ 个整数 $a_0,a_1,\cdots ,a_{n-1}$ 表示多项式的系数。

输出格式

第一行输出一个整数 $Q$，满足 $Q\le T$，表示你使用的操作数。接下来 $Q$ 行每行两个整数 $a_i,b_i$，表示一次操作。

样例一

input

4 2 1000000
0 1 1 0

output

2
1 0
2 0

explanation

初始时 $P(x)=x+x^2$。

第一次操作后，$P(x)$ 加上了 $x$，变成了 $x^2$。

第二次操作后，$P(x)$ 加上了 $x^2$，变成了 $0$。

当然，你也可以用一次操作 $1,1$ 把多项式变成 $0$。

样例二/三

见附件下载。

数据范围

对于全部数据：$1\le k\le 20$，$a_i\in \{0,1\}$，$1.6\times {10}^5\le T\le {10}^6$。

时间限制：$6\mathtt{\text{s}}$

空间限制：$1\mathtt{\text{GB}}$