T2 取石子

题目信息

时间限制: 1.5s

空间限制: 512M

输入文件: nim.in

输出文件: nim.out

题目描述

有 $n$ 堆石子，第 $i$ 堆石子有 $a_i$ 个。小明和小王轮流取（选中一堆，然后在其中取正整数个，不能不取），小明先手。

小明第一次可以取至多 $K$ 个石子，之后每个人取的石子数不能超过上一个人刚刚取的石子数。不能取的人输。

请你求出小明是否有必胜策略。如果有，你还需要求出他第一步的所有存在必胜策略的取法。

输入格式

第一行两个正整数 $n,K$。

第二行 $n$ 个正整数 $a_1, a_2,\dots , a_n$。

输出格式

第一行一个整数表示胜负。$1$ 表示小明有必胜策略，$0$ 表示小明没有必胜策略。

如果小明有必胜策略，接下来若干行每行输出两个整数 $x,y$ 表示小明第一步从第 $x$ 堆取 $y$ 个可以保证必胜。

输出顺序按照 $(x,y)$ 的字典序，即，如果 $x_1 < x_2$ 或 $x_1 = x_2 , y_1 < y_2$，$(x_1,y_1)$ 就比 $(x_2,y_2)$ 先输出。

样例

样例输入 1

5 3
1 3 6 8 2

样例输出 1

1
2 2
3 2
4 2
5 2

样例输入 2

3 2
1 3 3

样例输出 2

1
1 1
2 1
3 1

样例解释 2

小明第一步取 $1$ 个石子则后面每个人每次都只能取 $1$ 个石子，因为不能超过上一个人取的个数。因为总数是奇数，小明会取到最后一个石子，小王因为没有取石子而失败，小明必胜。

如果小明第一步取 $2$ 个石子，则小王第二步只要取 $1$ 个石子，之后小明必败。

数据范围与提示

对于所有数据，$1\le n\le 50000,1\le K, a_i\le 10^9$，保证先手有必胜策略的第一步操作种类数不超过 $2000000$。

对于 $20\%$ 的数据，$n\le 10, a_i\le 8$；

对于另外 $20\%$ 的数据，$a_i\le 3$；

对于另外 $20\%$ 的数据，$K\le 3$。