# 抽奖插件

- 参考时间限制：8.5 秒（参考环境：[评测环境与性能](../../../docs/评测环境与性能.md)；仅供预估）
- 实际时间限制：标准程序在目标评测环境中处理最慢正式测试文件的基准时间的 2 倍，按 0.5 秒的倍数向上取整；若平台仅支持更粗的粒度，再向上取整到平台可设置值。
- 内存限制：512 MB

## 背景故事

村长正在调试抽奖插件。参与者可以退出，也可以修改幸运数字并重新加入。插件需要在指定时刻找出幸运数字最接近目标值的人，并严格执行同分时的编号规则。

## 形式化问题描述

共有 $n$ 人，编号为 $1$ 到 $n$ .初始所有人都在场，编号 $i$ 的幸运数字为 $i$ .依次处理 $m$ 个事件。

令 $a_0=A$ ，对每个事件 $i$ 计算一次

$$a_i=(a_{i-1}B+C)\bmod n+1,\qquad t_i=a_i$$

事件分为三种：

1. **查询**：在场者中选幸运数字与 $t_i$ 的绝对差最小的人。差相同时选幸运数字更小的；幸运数字仍相同时，若该数字大于 $t_i$ ，选编号最小者，否则选编号最大者。无人时答案为 $0$ .查询不改变状态。
2. **修改**：给定编号 $d_i$ ，把该人的幸运数字改为 $t_i$ ；如果已经退出，则同时重新加入。
3. **退出**：让编号为 $t_i$ 的人退出；已经退出时没有变化。

输入给出 $q$ 个查询事件的位置，以及 $k$ 个修改事件的位置和对象。其他事件均为退出事件。每个事件都推进一次上述序列，包括查询和无效退出。

## 输入格式

第一行三个整数 $A,B,C$ .第二行四个整数 $n,m,q,k$ .第三行 $q$ 个严格递增的事件编号，表示查询位置。第四行 $k$ 对整数 $p_i,d_i$ ，表示第 $p_i$ 个事件修改参与者 $d_i$ ；其中 $p_i$ 严格递增。两类事件编号互不重叠。$q=0$ 或 $k=0$ 时对应行为空。

## 输出格式

按事件顺序输出 $q$ 行，每行一个查询结果。$q=0$ 时不输出任何整数。

## 样例 1

### 输入

```text
5 3 3
5 8 4 2
3 6 7 8
2 3 5 3
```

### 输出

```text
2
1
2
3
```

## 样例 2

### 输入

```text
1 13 17
11 30 10 8
5 13 17 18 19 20 23 25 27 30
1 1 8 1 9 1 15 10 21 10 26 4 28 4 29 10
```

### 输出

```text
7
4
4
6
8
4
4
7
6
4
```

## 样例 3

### 输入

```text
1 1 17
11 60 15 8
5 13 17 18 19 20 23 25 27 30 40 45 55 58 60
1 1 8 1 9 1 15 10 21 10 26 4 28 4 29 10
```

### 输出

```text
3
3
9
10
2
9
9
9
2
2
2
0
0
0
0
```

## 样例解释

样例 1 的目标值依次为 $4,1,2,5,4,1,2,5$ ，四次查询结果为 $2,1,2,3$ .样例 3 后四次查询时所有人都已退出，因此输出 $0$ .

## 数据范围与保证

所有数据满足 $1\le n\le3500000$ ，$0\le m\le4000000$ ，$0\le q,k\le200000$ ，$q+k\le m$ ，$0\le A,B,C\le10^9$ .所有事件编号在 $[1,m]$ 内，修改对象编号在 $[1,n]$ 内。

| 分值比例 | 额外条件 |
| --- | --- |
| 100% | 无额外条件 |