Problem Statement

Takahashi has created a game where the player controls a dragon on a coordinate plane.

The dragon consists of N parts numbered 1 to N, with part 1 being called the head.

Initially, part i is located at the coordinates (i,0). Process Q queries as follows.

• 1 C: Move the head by 1 in direction C. Here, C is one of R, L, U, and D, which represent the positive x-direction, negative x-direction, positive y-direction, and negative y-direction, respectively. Each part other than the head moves to follow the part in front of it. That is, part i (2\leq i \leq N) moves to the coordinates where part i-1 was before the move.
• 2 p: Find the coordinates of part p.

Constraints

• 2 \leq N \leq 10^6
• 1 \leq Q \leq 2\times 10^5
• For the first type of query, C is one of R, L, U, and D.
• For the second type of query, 1\leq p \leq N.
• All numerical input values are integers.

Sample Input 1

5 9
2 3
1 U
2 3
1 R
1 D
2 3
1 L
2 1
2 5

Sample Output 1

3 0
2 0
1 1
1 0
1 0

At each time when processing the second type of query, the parts are at the following positions:

Note that multiple parts may exist at the same coordinates.

Problem Statement

Takahashi is planning an N-day train trip.
For each day, he can pay the regular fare or use a one-day pass.

Here, for 1\leq i\leq N, the regular fare for the i-th day of the trip is F_i yen.
On the other hand, a batch of D one-day passes is sold for P yen. You can buy as many passes as you want, but only in units of D.
Each purchased pass can be used on any day, and it is fine to have some leftovers at the end of the trip.

Find the minimum possible total cost for the N-day trip, that is, the cost of purchasing one-day passes plus the total regular fare for the days not covered by one-day passes.

Constraints

• 1\leq N\leq 2\times 10^5
• 1\leq D\leq 2\times 10^5
• 1\leq P\leq 10^9
• 1\leq F_i\leq 10^9
• All input values are integers.

Sample Input 1

5 2 10
7 1 6 3 6

Sample Output 1

20

If he buys just one batch of one-day passes and uses them for the first and third days, the total cost will be (10\times 1)+(0+1+0+3+6)=20, which is the minimum cost needed.
Thus, print 20.

Sample Input 2

3 1 10
1 2 3

Sample Output 2

6

The minimum cost is achieved by paying the regular fare for all three days.

Sample Input 3

8 3 1000000000
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000

Sample Output 3

3000000000

The minimum cost is achieved by buying three batches of one-day passes and using them for all eight days.
Note that the answer may not fit into a 32-bit integer type.

Problem Statement

You are given a sequence of positive integers: A=(a_1,a_2,\ldots,a_N).
You can choose and perform one of the following operations any number of times, possibly zero.

• Choose an integer i such that 1 \leq i \leq N and a_i is a multiple of 2, and replace a_i with \frac{a_i}{2}.
• Choose an integer i such that 1 \leq i \leq N and a_i is a multiple of 3, and replace a_i with \frac{a_i}{3}.

Your objective is to make A satisfy a_1=a_2=\ldots=a_N.
Find the minimum total number of times you need to perform an operation to achieve the objective. If there is no way to achieve the objective, print -1 instead.

Constraints

• 2 \leq N \leq 1000
• 1 \leq a_i \leq 10^9
• All values in the input are integers.

Sample Input 1

3
1 4 3

Sample Output 1

3

Here is a way to achieve the objective in three operations, which is the minimum needed.

• Choose an integer i=2 such that a_i is a multiple of 2, and replace a_2 with \frac{a_2}{2}. A becomes (1,2,3).
• Choose an integer i=2 such that a_i is a multiple of 2, and replace a_2 with \frac{a_2}{2}. A becomes (1,1,3).
• Choose an integer i=3 such that a_i is a multiple of 3, and replace a_3 with \frac{a_3}{3}. A becomes (1,1,1).

Sample Input 2

3
2 7 6

Sample Output 2

-1

There is no way to achieve the objective.

Sample Input 3

6
1 1 1 1 1 1

Sample Output 3

0

Problem Statement

Integer Sequence Exhibition is taking place, where integer sequences are gathered in one place and evaluated. Here, every integer sequence of length N consisting of integers between 1 and K (inclusive) is evaluated and given an integer score between 1 and M (inclusive).

Print the number, modulo 998244353, of ways to give each of the evaluated sequences a score between 1 and M.

Here, two ways are said to be different when there is an evaluated sequence A = (A_1, A_2, \ldots, A_N) that is given different scores by the two ways.

Constraints

• 1 \leq N, K, M \leq 10^{18}
• N, K, and M are integers.

Sample Input 1

2 2 2

Sample Output 1

16

Four sequences are evaluated: (1, 1), (1, 2), (2, 1), and (2, 2). There are 16 ways to give each of these sequences a score between 1 and 2, as follows.

• Give 1 to (1, 1), 1 to (1, 2), 1 to (2, 1), and 1 to (2, 2)
• Give 1 to (1, 1), 1 to (1, 2), 1 to (2, 1), and 2 to (2, 2)
• Give 1 to (1, 1), 1 to (1, 2), 2 to (2, 1), and 1 to (2, 2)
• Give 1 to (1, 1), 1 to (1, 2), 2 to (2, 1), and 2 to (2, 2)
• \cdots
• Give 2 to (1, 1), 2 to (1, 2), 2 to (2, 1), and 2 to (2, 2)

Thus, we print 16.

Sample Input 2

3 14 15926535

Sample Output 2

109718301

Be sure to print the count modulo 998244353.

Problem Statement

You are given an integer sequence A = (A_1, A_2, \ldots, A_N) of length N.

We will perform the following operation on A for i = 1, 2, \ldots, M in this order.

• First, choose an integer between L_i and R_i, inclusive, uniformly at random and denote it as p.
• Then, change the value of A_p to the integer X_i.

For the final sequence A after the above procedure, print the expected value, modulo 998244353, of A_i for each i = 1, 2, \ldots, N.

Constraints

• All input values are integers.
• 1 \leq N, M \leq 2 \times 10^5
• 0 \leq A_i \leq 10^9
• 1 \leq L_i \leq R_i \leq N
• 0 \leq X_i \leq 10^9

Sample Input 1

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

Sample Output 1

499122179 1 665496238 665496236 5

We start from the initial state A = (3, 1, 4, 1, 5) and perform the following two operations.

• The first operation chooses A_1 or A_2 uniformly at random, and changes its value to 2.
• Then, the second operation chooses one of A_2, A_3, A_4 uniformly at random, and changes its value to 0.

As a result, the expected values of the elements in the final A are (E_1, E_2, E_3, E_4, E_5) = (\frac{5}{2}, 1, \frac{8}{3}, \frac{2}{3}, 5).

Sample Input 2

2 4
1 2
1 1 3
2 2 4
1 1 5
2 2 6

Sample Output 2

5 6

Sample Input 3

20 20
998769066 273215338 827984962 78974225 994243956 791478211 891861897 680427073 993663022 219733184 570206440 43712322 66791680 164318676 209536492 137458233 289158777 461179891 612373851 330908158
12 18 769877494
9 13 689822685
6 13 180913148
2 16 525285434
2 14 98115570
14 17 622616620
8 12 476462455
13 17 872412050
14 15 564176146
7 13 143650548
2 5 180435257
4 10 82903366
1 2 643996562
8 10 262860196
10 14 624081934
11 13 581257775
9 19 381806138
3 12 427930466
6 19 18249485
14 19 682428942

Sample Output 3

821382814 987210378 819486592 142238362 447960587 678128197 687469071 405316549 318941070 457450677 426617745 712263899 939619994 228431878 307695685 196179692 241456697 12668393 685902422 330908158