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

In the xy-plane, we have N points numbered 1 through N.
Point i is at the coordinates (X_i,Y_i). Any two different points are at different positions.
Find the number of ways to choose three of these N points so that connecting the chosen points with segments results in a triangle with a positive area.

Constraints

• All values in input are integers.
• 3 \le N \le 300
• -10^9 \le X_i,Y_i \le 10^9
• (X_i,Y_i) \neq (X_j,Y_j) if i \neq j.

Sample Input 1

4
0 1
1 3
1 1
-1 -1

Sample Output 1

3

The figure below illustrates the points.

There are three ways to choose points that form a triangle: \{1,2,3\},\{1,3,4\},\{2,3,4\}.

Sample Input 2

20
224 433
987654321 987654321
2 0
6 4
314159265 358979323
0 0
-123456789 123456789
-1000000000 1000000000
124 233
9 -6
-4 0
9 5
-7 3
333333333 -333333333
-9 -1
7 -10
-1 5
324 633
1000000000 -1000000000
20 0

Sample Output 2

1124

Problem Statement

You are given a sequence of positive integers A=(a_1,\ldots,a_N) of length N.
There are (2^N-1) ways to choose one or more terms of A. How many of them have an integer-valued average? Find the count modulo 998244353.

Constraints

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

Sample Input 1

3
2 6 2

Sample Output 1

6

For each way to choose terms of A, the average is obtained as follows:

• If just a_1 is chosen, the average is \frac{a_1}{1}=\frac{2}{1} = 2, which is an integer.

• If just a_2 is chosen, the average is \frac{a_2}{1}=\frac{6}{1} = 6, which is an integer.

• If just a_3 is chosen, the average is \frac{a_3}{1}=\frac{2}{1} = 2, which is an integer.

• If a_1 and a_2 are chosen, the average is \frac{a_1+a_2}{2}=\frac{2+6}{2} = 4, which is an integer.

• If a_1 and a_3 are chosen, the average is \frac{a_1+a_3}{2}=\frac{2+2}{2} = 2, which is an integer.

• If a_2 and a_3 are chosen, the average is \frac{a_2+a_3}{2}=\frac{6+2}{2} = 4, which is an integer.

• If a_1, a_2, and a_3 are chosen, the average is \frac{a_1+a_2+a_3}{3}=\frac{2+6+2}{3} = \frac{10}{3}, which is not an integer.

Therefore, 6 ways satisfy the condition.

Sample Input 2

5
5 5 5 5 5

Sample Output 2

31

Regardless of the choice of one or more terms of A, the average equals 5.

Problem Statement

There are N people numbered from 1 to N standing in a circle. Person 1 is to the right of person 2, person 2 is to the right of person 3, ..., and person N is to the right of person 1.

We will give each of the N people an integer between 0 and M-1, inclusive.
Among the M^N ways to distribute integers, find the number, modulo 998244353, of such ways that no two adjacent people have the same integer.

Constraints

• 2 \leq N,M \leq 10^6
• N and M are integers.

Sample Input 1

3 3

Sample Output 1

6

There are six desired ways, where the integers given to persons 1,2,3 are (0,1,2),(0,2,1),(1,0,2),(1,2,0),(2,0,1),(2,1,0).

Sample Input 2

4 2

Sample Output 2

2

There are two desired ways, where the integers given to persons 1,2,3,4 are (0,1,0,1),(1,0,1,0).

Sample Input 3

987654 456789

Sample Output 3

778634319

Be sure to find the number modulo 998244353.

Problem Statement

You are given N intervals numbered 1 to N. Interval i is [L_i, R_i].

Two intervals [l_a, r_a] and [l_b, r_b] are said to intersect if and only if they satisfy either (l_a < l_b < r_a < r_b) or (l_b < l_a < r_b < r_a).

Define f(l, r) as the number of intervals i (1 \leq i \leq N) that intersect with the interval [l, r].

Among all pairs of integers (l, r) satisfying 0 \leq l < r \leq 10^{9}, find the pair (l, r) that maximizes f(l, r). If there are multiple such pairs, choose the one with the smallest l. If there are still multiple pairs, choose the one with the smallest r among them. (Since 0 \leq l < r, the pair (l, r) to be answered is uniquely determined.)

Constraints

• 1 \leq N \leq 10^{5}
• 0 \leq L_i < R_i \leq 10^{9} (1 \leq i \leq N)
• All input values are integers.

Sample Input 1

5
1 7
3 9
7 18
10 14
15 20

Sample Output 1

4 11

The maximum value of f(l, r) is 4, and among the pairs (l, r) that achieve f(l, r) = 4, the smallest l is 4. The pairs (l, r) that satisfy f(l, r) = 4 and l = 4 are the following five:

• (l, r) = (4, 11)
• (l, r) = (4, 12)
• (l, r) = (4, 13)
• (l, r) = (4, 16)
• (l, r) = (4, 17)

Among these, the smallest r is 11, so print 4 and 11.

Sample Input 2

11
856977192 996441446
298251737 935869360
396653206 658841528
710569907 929136831
325371222 425309117
379628374 697340458
835681913 939343451
140179224 887672320
375607390 611397526
93530028 581033295
249611310 775998537

Sample Output 2

396653207 887672321