#46. 【清华集训2014】玄学

1. 巨酱想到了一种操作，能让耳机的玄学值由 $x$ 变为 $(ax + b) \bmod m$，并且他计划对编号为 $i$ 到 $j$ 的耳机执行这种操作。
2. 巨酱想知道如果将（并且仅将）自己的第 $i$ 个到第 $j$ 个计划按顺序付诸行动，编号为 $k$ 的耳机的玄学值将会变成多少。

样例一

input

24
3 5
1 2 3
5
1 1 2 3 2
1 2 3 4 3
2 1 1 3
1 1 3 1 4
2 1 3 2



output

3
4



样例二

input

7
3 5
1 2 3
5
1 1 2 0 3
1 2 3 4 0
2 1 1 3
1 2 0 2 0
2 2 0 1



output

3
4



限制与约定

1 ~ 2 $20$ $20$ xxxxx
3 ~ 4 $100000$ $100000$ 0001x
5 ~ 6 $100000$ $100000$ 1110x
7 ~ 8 $100000$ $100000$ 1111x
9 ~ 10 $100000$ $100000$ 0010x
11 ~ 15 $100000$ $100000$ xxxxx
16 ~ 20 $100000$ $600000$ xxxxx