UOJ Logo Universal Online Judge

UOJ

附件下载 统计

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

这个迷宫看似容易,但在小青鱼即将走出迷宫的时候,却被 $n=2^k$ 个比特机器人拦住了去路。这些机器人从左到右显示着 $a_0,a_1,\cdots,a_{n-1}$,表示一个 $n-1$ 次的多项式 $P(x)=a_0+a_1x+\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) \bmod 2$,其中 $\bmod 2$ 表示对 $2$ 取模。

整体来看,这个操作的作用是将这个多项式 $P(x)$ 在 $\bmod 2$ 意义上加上 $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\leq k\leq 20$,$a_i \in \{0,1\}$,$1.6\times 10^5 \leq T \leq 10^6$。

子任务编号 $k\leq$ $T \geq$ 分值
$\text{1}$ $17$ $1.6\times 10^5$ $10$
$\text{2}$ $20$ $3\times 10^5$ $20$
$\text{3}$ $20$ $1.8\times 10^5$ $30$
$\text{4}$ $20$ $1.6\times 10^5$ $40$

时间限制:$6\texttt{s}$

空间限制:$1\texttt{GB}$