1
地图上有 $n$ 个格子排成一排, 最左边的格子为 1 , 最右边的格子为 $n$ 。
第 0 秒时, 每个格子都有一只史莱姆。
第 $i$ 只史莱姆的跳跃方向用数组 $a$ 表示。
$a_i=0$ 表示史莱姆跳跃的方向是往左。若第 $i$ 秒史莱姆位于格子 $x$, 那么第 $i+1$ 秒史莱姆会跳到格子 $x-1$ 。如果当前史莱姆在格子 1 , 则下一秒史莱姆将跳出地图。
$a_i=1$ 表示史莱姆跳跃的方向是往右。若第 $i$ 秒史莱姆位于格子 $x$, 那么第 $i+1$ 秒史莱姆会跳到格子 $x+1$ 。如果当前史莱姆在格子 $n$, 则下一秒史莱姆将跳出地图。
米小游想知道第 $1 \sim n$ 秒, 地图上有多少个格子没有史莱姆。
1 输入描述
第一行包含一个整数 $n\left(1 \leq n \leq 3 \times 10^3\right)$, 表示地图上的格子数量。
第二行包含 $n$ 个整数 $a_i\left(0 \leq a_i \leq 1\right)$, 表示每只史莱姆的跳跃方向。
I输出描述
输出包含一行 $n$ 个整数, 用空格隔开, 第 $i$ 个数表示第 $i$ 秒没有史莱姆的格子数量。
输入：
3
1 0 1
输出：
1 2 3
使用python3编写代码，只允许使用 import sys
说明：
史莱姆 $1 \sim 3$ 的跳跃方向分别为, 往右, 往左, 往右。
第 1 秒, 史莱姆 1 跳到格子 2 , 史莱姆 2 跳到格子 1 史莱姆 3 跳出地图, 格子 3 没有史莱姆。
第 2 秒, 史莱姆 1 跳到格子 3 , 史莱姆 2 跳出地图,格子 1,2 没有史莱姆。
第 3 秒, 史莱姆 1 跳出地图, 格子 $1,2,3$ 没有史莱姆。
2
仙舟罗浮上有一棵建木, 据说服下建木生成的神实就可以得到“无尽形寿”的身体, 蜕变为长生种。米小游是短生种, 因此她很想找到神实。
建木是一棵有 $n$ 个节点的有根树, 节点编号为 $1 \sim n$, 根节点为 $x$ 。
对于编号为 $i$ 的节点, $f(i)$ 表示以 $i$ 为根的子树中, 节点编号是 $i$ 的因子的节点个数。
建木上神实的总数就是 $\sum_{i=1}^n f(i)$, 米小游想知道建木上神实的总数是多少。
| 输入描述
第一行包含两个整数 $n, x\left(1 \leq x \leq n \leq 5 \times 10^5\right)$, 表示树的节点个数, 根节点编号。
接下来 $n-1$ 行, 每行两个整数 $u, v(1 \leq u, v \leq n)$,表示一条 $u$ 到 $v$ 的树边。
数据保证一定是一棵树。
输出描述：
输出包含一个整数，表示建木上神实的总数。
输入：
4 4
1 2
4 3
2 4
输出：
7
说明：
以节点 4 为根的子树的节点有 $[1,2,3,4]$, 其中 $[1,2,4]$ 是 4 的因子, $f(4)=3$ 。
以节点 2 为根的子树的节点有 $[1,2]$, 其中 $[1,2]$ 是 2 的因子, $f(2)=2$ 。
以节点 1 为根的子树的节点有 [1]，其中 [1] 是 1 的因子, $f(1)=1$ 。
以节点 3 为根的子树的节点有 [3], 其中 [3] 是3的因子, $f(3)=1$ 。
$$
\sum_{i=1}^n f(i)=1+2+1+3=7 \text { 。 }
$$
3
本题目由抽崩坏三茶歌时刻一番赏真实事件改（乱）编！
一番赏初始有 $n$ 个抽赏, 大家需要排队购买, 只有在队列最前面的人可以选择购买或者不购买, 所有人随时都可以离开队列，离开队列后也可以随时加入队列。
米小游陪着她的好朋友莫娜来买一番赏，她时不时会看一眼队列中有多少人。也就是说, 共有 4 种事件:
1. $1 \mathrm{~s}$ : 名字为 $s$ 的人加入队列的结尾 (保证 $s$ 不在队列中)
$2.2 \mathrm{~s}$ : 名字为 $s$ 的人离开队列（保证 $s$ 在队列中, 但不一定在队列最前面)
3. $3 x$ : 队列最前面的人购买了 $x$ 个抽赏（保证在抽赏个数大于 0 时，当前至少有 $x$ 个抽赏）。
4. 4 : 米小游查看队列人数。
还有一个特殊规则：当抽赏个数小于等于 $m$ 时, 处于队列最前面的人一定会把剩余的所有抽赏全部买走。当抽赏全部被买走后, 队列会立即清空, 后续的所有事件都将失效。
米小游想知道, 她每次查看队列人数时, 队列中有多少人。以及最后抽赏全部卖完或者所有事件结束后, 每个参与过排队的人各买了多少个抽赏? (按名字字典序升序输出)
| 输入描述
第一行输入三个整数
$n, m\left(1 \leq m \leq n \leq 10^9\right), q\left(1 \leq q \leq 2 \times 10^5\right)$ 表示抽赏个数、特殊规则限制、事件个数。
接下来 $q$ 行, 首先输入一个整数 $o p(1 \leq o p \leq 4)$ 表示事件类型:
若事件类型为 1 或 2 ，则再输入一个长度不超过 10 的只由大小写字母组成的字符串 $s$ 表示名字;
若事件类型为 3 , 则再输入一个整数 $x$ 表示购买的抽赏个数;
若事件类型为 4 , 则不再输入。
1 输出描述
对于每一个类型为 4 的事件，输出一行，包含一个整数表示队列中的人数。
最后每一行按字典序升序输出每一个参与过排队的人的名字和购买的抽赏个数 (用一个空格隔开)。
输入：
70 20 8
1 Mona
1 Kaveh
4
2 Mona
1 Mona
2 Kaveh
4
1 Kaveh
输出：
2
1
Kaveh 0
Kaveh 0
