1097: 贵校是泰拉瑞亚王国吗
Description
Sword Dancer 队赛前开黑泰拉瑞亚，就能在比赛中取得佳绩，否则就会打铁。昨天你玩泰拉瑞亚了吗？
有 $n$ 种物品，编号为 $1,2,…,n$；给定长度为 $n$ 的正整数序列 $s_1,s_2,…,s_n$，其中 $s_i$ 表示物品 $i$ 在单个栏位中的最大堆叠数。有 $m$ 名玩家，$q$ 次存放，一个箱子有 $v$ 个栏位，初始有 $0$ 个箱子。给定每次存放的玩家编号 $p$、待存栏位数 $k$、每栏物品编号 $x$ 和个数 $y$。
存放时对待存栏位顺序依次执行如下过程：若该种物品存在于未满的箱子中，则将该物品尽可能多地存入该箱子（不同种物品不能堆叠在一栏）；若当前待存栏位仍有剩余物品，将其放入编号最小的有空栏位的箱子中。（若不存在有空栏位的箱子，则玩家 $p$ 先放置一个编号为 $当前箱子数+1$ 的空箱子再继续存放）
求依次完成所有存放后，每个玩家放置的箱子个数。
Input
第一行输入四个整数 $n,m,q,v(1\leq n,m,q\leq2\times 10^5,1\leq v\leq10^3)$，表示物品种类数、玩家人数、存放次数和箱子栏位数。
第二行输入 $n$ 个正整数 $s_1,s_2,…,s_n(1\le s_i\le 10^3)$，其中 $s_i$ 表示物品 $i$ 在单个栏位中的最大堆叠数。
接下来 $2\times q$ 行，每次存放两行：
第一行输入两个整数 $p,k(1\le p\le m,1\le k\le2\times10^5)$，表示玩家编号和待存栏位数。
第二行输入 $k$ 对整数 $x_1,y_1,x_2,y_2,…,x_k,y_k(1\le x_i\le n,1\le y_i\le s_{x_i})$，$x_i,y_i$ 表示第 $i$ 栏的物品种类和个数。
输入保证 $\sum k\le2\times10^5$。
Output
Sample Input Copy
2 2 2 2
2 3
1 2
1 1 1 2
2 2
2 3 1 2Sample Output Copy
1 1HINT
第一次存放，存入第一栏后的箱子状态为 $[[1,1],[\ ,\ ]]$，存入第二栏后的箱子状态为 $[[1,2],[1,1]]$。
第二次存放，存入第一栏后的箱子状态为 $[[1,2],[1,1]],[[2,3],[\ ,\ ]]$，存入第二栏后的箱子状态为 $[[1,2],[1,2]],[[2,3],[1,1]]$。