P5222 Game

Justin摆弄着他的棋盘和棋...突然，他想到了一个非常好玩的游戏。

棋盘可以看做是一个$N \times M$的网格，~~由于Justin太健壮了，~~所以他把$T$个格子弄坏了。也就是说，上面没法放棋子。 Justin想到的游戏是这样的：一开始，你可以选择棋盘的第一列的一些没有坏的格子，在上面各放上一枚棋子。然后，你可以执行依次以下操作若干次： 1. 选择一枚棋子，将其向上或者向下移动到**相邻**的一个好的且**没有其他棋子**的格子上。 2. 将所有棋子移动到下一列。若移动到下一列后有**任意一个**棋子落在坏的格子上，则不能执行此操作。 Justin现在给了你$Q$个问题，每一次给你一个$k_i$，询问你最多能在第一列上放多少枚棋子使得经过若干次操作后你能将所有棋子移动到最后一列，且**所有棋子加起来**最多执行$k_i$次1操作。 (感谢巨佬ywwywwyww 发现题目问题，现已修复。)

无

无

第一组样例：限制为0时，可以在(3,1)放置一枚棋子，然后一直执行二操作。 限制为1时，可以在(3,1)放置一枚棋子，在(2,1)放置一枚棋子，然后执行两次二操作之后对(2,3)上的棋子执行一次一操作到(1,3)，然后一直执行二操作就好了。 限制为2时，和上面一样。因为如果放置三枚棋子的话是没办法执行操作二的。 第二组样例：发现完全堵死了，所以根本不可能移动到最后一列。 数据范围： |测试点编号|$N\le$|$M\le$|$T\le$|$Q\le$| |:-------:|:-------:|:-------:|:-------:|:-------:| |$1$|$1$|$10^6$|$1$|$10^5$| |$2-6$|$10$|$100$|$10$|$100$| |$7-10$|$20$|$100$|$50$|$10^3$| |$11-14$|$30$|$10^4$|$100$|$10^4$| |$15-20$|$50$|$10^6$|$10^3$|$10^5$| $$1 \le x_i \le N \qquad 1\le y_i \le M \qquad 0 \le k_i \le 2^{31}-1$$ 此题测试点$11$~$20$的数据随机生成。