You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Background

Special for beginners, ^_^

Description

东东最近在研究广义斐波那契数列，已知 $x, y$，定义长度为 $n$ 的数列 ${a_n}$，其中

$a_1=a_2=1$，

当 $i\ge 2$, 有 $a_i = x*a_{i-1}+y*a_{i-2}$。

如 $x=1,y=2$时，$a={1,1,3,5,11,21,43,...}$

他在研究其中数字出现的频率。

定义 $b_i = a_i \mod m$。 mod为 求余数操作。

如 5 mod 3 = 2; 19 mod 4 = 3; 20 mod 4 = 0.

有 $q$ 个问题， 每个问题给出一个范围 $l,r$ 和一个数值 $v$， 问 $b_l,b_{l+1},....,b_r$ 之间有多少个$v$。

Format

Input

第一行五个正整数 $n, x, y, m, q$。 接下来$q$行，每行三个正整数 $l,r,v$，表示问题。

Output

$q$ 行，每行一个答案，表示 $b_l,b_{l+1},....,b_r$ 之间有多少个$v$。

Samples

7 1 2 3 3
1 7 0
1 7 1
1 7 2

2
3
2

$a={1,1,3,5,11,21,43}$

$b={1,1,0,2,2,0,1}$

Limitation

30% $n, q \le 1000$

另有30% $m=3$

100% $1 \le n, m, x, y, q \le 10^5$, $0\le v\lt m$