L. Las Tortuguitas
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

Dudu is on a magical journey inside the Fantastic Chocolate Factory and discovered a secret room full of machines that produce extremely rare candies called "Tortuguitas". This room contains $$$N$$$ machines numbered from $$$1$$$ to $$$N$$$, and each machine produces exactly $$$K$$$ Tortuguitas, numbered from $$$1$$$ to $$$K$$$.

A machine is represented by the rarity of the Tortuguitas it produces. More formally, the $$$i$$$-th machine produces $$$K$$$ Tortuguitas with rarities $$$r_{i, 1}, r_{i, 2}, \cdots, r_{i, K}$$$. Let $$$X$$$ be the rarity value of the simplest Tortuguita, and the rarity of a Tortuguita can be calculated as follows.

  • $$$ \large r_{i, j} = j \cdot X$$$ for all $$$(1 \le j \le K)$$$, when $$$i = 1$$$.
  • $$$ \large r_{i, j} = \displaystyle \sum_{t = 1}^{j} r_{i - 1, t}$$$, when $$$i \gt 1$$$.

Dudu was amazed by these magical machines and asked for your help to answer some questions about them.

He will give you $$$Q$$$ questions of the following type: In the $$$i$$$-th machine, what is the sum of the rarities of the Tortuguitas numbered greater than or equal to $$$L$$$ and less than or equal to $$$R$$$?

More formally, Dudu will ask for the result of $$$\displaystyle \sum_{j = L}^{R} r_{i, j}$$$.

Since this result can be absurdly large, he only wants you to return the remainder of this sum when divided by $$$998244353$$$.

Input

The first line of input contains $$$4$$$ integers $$$N$$$, $$$K$$$, $$$Q$$$, and $$$X$$$ $$$(1 \le N, K, Q \le 3 \cdot 10^5)$$$ $$$(1 \le X \lt 998244353)$$$ — the number of machines, the number of Tortuguitas each machine produces, the number of questions Dudu asked, and the rarity of the simplest Tortuguita, respectively.

The next $$$Q$$$ lines each contain $$$3$$$ integers $$$i$$$, $$$L$$$, and $$$R$$$ $$$(1 \le i \le N)$$$ $$$(1 \le L \le R \le K)$$$, the machine number and the range for which Dudu wants to know the sum.

Output

The output should contain $$$Q$$$ lines, each with the result of the sum modulo 998244353.

Examples
Input
3 10 3 5
1 4 7
2 4 7
3 4 7
Output
110
370
975
Input
50 100 2 7
4 1 10
50 3 100
Output
14014
574802200
Input
1 1 1 1
1 1 1
Output
1