题目描述

仿射变换在密码学中，是一种由移位加密（凯撒密码）进化而来的加密算法。

我们假定 $x$ 为明文，$y$ 为密文（$x,y$ 均为整数），整数 $a,b,m$ 是我们加密明文所用的三个变量，则仿射变换过程如下：

Macesuted 今天想使用仿射加密加密他的数据，但是他觉得这种加密算法太弱了。于是 Macesuted 想出了一种方法使这种加密算法变得稍强——对同一个数字做多次仿射变换。

由于他的记性不好，他会先告诉你加密的参数 $a,b,m$，所有数据的加密都使用这三个参数。

然后他会给你很多个数据，数据是一个小于 $m$ 的整数，由于他觉得不同数据的重要程度不同，所以他还会告诉你对于每一个数据你分别需要加密的次数 $k$。

现在请你告诉 Macesuted 这些数据加密后的密文。

输入格式

第一行四个整数 $a,b,m,n$ ，其中 $a,b,m$ 含义如上，$n$ 表示将要给出的数据数量。
接下来 $n$ 行，每行两个整数 $data,k$，分别表示 Macesuted 给出的数据，和这个数据需要加密的次数。

输出格式

共 $n$ 行，每行一个整数表示 Macesuted 的数据在对应的询问下的加密结果。

2 3 10 2
7 3
5 2

7
9

数据规模与约定

对于 $50\%$ 的数据，$\sum k\le10^8$。
对于 $100\%$ 的数据，$1\le n\le 10^5$，$1\le k \le 10^8$，$0< a,b< m\le10^5$，$0\le data< m$。