Problem Statement

Takahashi is walking along a path with N points arranged in a line. The points are numbered 1, 2, \ldots, N from left to right, where smaller numbers are on the left and larger numbers are on the right.

There are M coins scattered along this path, each placed at a specific point. The i-th coin is placed at point P_i and has a value of V_i. Multiple coins may be placed at the same point.

Takahashi starts at point S and moves to point T. The movement rules are as follows:

• When S < T: He moves one point at a time to the right (in the direction of increasing numbers) in the order S, S+1, S+2, \ldots, T, visiting each point exactly once.
• When S > T: He moves one point at a time to the left (in the direction of decreasing numbers) in the order S, S-1, S-2, \ldots, T, visiting each point exactly once.
• When S = T: He does not move and stays at point S.

In all cases, both the starting point S and the destination point T are included in the visited points.

When Takahashi visits a point, he picks up all coins placed at that point.

Find the total value of the coins Takahashi picks up when he moves from point S to point T. If he does not pick up any coins, the total is 0.

Constraints

• 1 \leq N \leq 10^9
• 0 \leq M \leq 2 \times 10^5
• 1 \leq S \leq N
• 1 \leq T \leq N
• 1 \leq P_i \leq N (1 \leq i \leq M)
• 1 \leq V_i \leq 10^4 (1 \leq i \leq M)
• All input values are integers.

Sample Input 1

10 5 3 7
1 100
3 10
5 20
5 30
7 40

Sample Output 1

100

Sample Input 2

8 4 6 2
2 5
4 10
6 20
8 100

Sample Output 2

35

Sample Input 3

100 12 20 75
5 100
20 1
25 2
30 3
40 4
40 5
60 6
75 7
76 1000
90 9
55 10
10 11

Sample Output 3

38

Sample Input 4

1000000000 30 800000000 200000000
1 9999
1000000000 8888
800000000 10000
200000000 1
500000000 1234
750000000 4321
250000000 2222
199999999 7777
800000001 6666
600000000 3456
600000000 6544
300000000 1111
400000000 2222
700000000 3333
900000000 4444
100000000 5555
650000000 1010
550000000 2020
450000000 3030
350000000 4040
210000000 5050
790000000 6060
205000000 7070
795000000 8080
123456789 9090
987654321 123
333333333 321
666666666 654
777777777 987
222222222 789

Sample Output 4

73555

Sample Input 5

1 0 1 1

Sample Output 5

0

Problem Statement

Takahashi operates a robot in a corridor consisting of N rooms numbered from 1 to N arranged in a row. Each room i (1 \leq i \leq N) contains one treasure with value A_i.

The robot is given a command sequence S of length Q. The robot starts in room 1 with a score of 0, and executes the command sequence one character at a time from the beginning. The meaning of each character is as follows:

• L: If the current room number is greater than 1, move left (to the room with number 1 smaller). Otherwise, do nothing.
• R: If the current room number is less than N, move right (to the room with number 1 larger). Otherwise, do nothing.
• P: If the treasure in the current room has not yet been collected, collect it and add its value to the score. If it has already been collected, do nothing.
• B: Move to room 1.

Aoki performs M operations on the command sequence S in order. There are two types of operations:

• 1 p c: Replace the p-th character of the command sequence S with character c.
• 2: Determine the final score when the robot executes the current command sequence S.

For each operation 2, the robot starts from room 1 with all treasures uncollected and a score of 0, and executes the command sequence S from this initial state. This execution is a simulation to answer the query, and apart from the replacements to the command sequence S, the result of each operation does not affect other operations.

For each operation 2, output the answer.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq Q \leq 10^5
• 1 \leq M \leq 10^5
• 1 \leq A_i \leq 10^9
• S is a string of length Q consisting of L, R, P, B.
• In replacement operations, 1 \leq p \leq Q and c is one of L, R, P, B.
• At least one operation 2 is given.
• Letting K be the number of operation 2 queries, KQ \leq 2 \times 10^7.
• N, Q, M, A_i, p are all integers.

Sample Input 1

5 8 6
3 10 5 8 2
PRRPLPBR
2
1 2 P
2
1 7 R
1 8 P
2

Sample Output 1

18
13
13

Sample Input 2

3 7 7
4 7 9
LLPPRRB
2
1 1 R
2
1 4 B
2
1 7 P
2

Sample Output 2

4
4
4
13

Sample Input 3

10 24 15
6 1 13 8 21 5 34 2 55 3
PRRPRRPLLBPRRPPBLLRPRBRP
2
1 10 R
2
1 1 B
1 18 P
2
1 24 L
2
1 6 B
1 7 R
2
1 15 L
2
1 3 P
2

Sample Output 3

41
54
54
54
28
28
15

Sample Input 4

30 80 25
12 45 7 100 23 56 89 14 67 31 90 4 28 73 11 62 39 85 16 54 200 3 99 41 77 25 68 150 8 33
PRRPLBRRPPBLLRPRBPLRRRPPBPLLRPRRBLPPRRLBPBRRLLPPRBRPLLRRPPBBRPLPBRRPPBLLRPRRLBPP
2
1 6 R
1 20 P
2
1 35 B
1 48 P
2
1 1 L
1 80 B
2
1 12 P
1 13 R
1 14 R
2
1 50 L
1 51 L
2
1 60 P
1 70 B
2
1 25 R
2
1 40 P
1 41 P
2

Sample Output 4

164
87
87
87
87
87
87
187
187

Sample Input 5

1 1 9
1000000000
P
2
1 1 L
2
1 1 R
2
1 1 B
2
1 1 P
2

Sample Output 5

1000000000
0
0
0
1000000000

Problem Statement

Takahashi found N sweets in a sweet shop. The calorie of the i-th sweet (1 \leq i \leq N) is a positive integer A_i.

Takahashi wants to make an assortment by choosing one or more of these sweets. He is very particular about calorie control and wants the sum of the calories of the chosen sweets to be divisible by K.

Find the number of ways to choose sweets that satisfy this condition. Specifically, find the number of non-empty subsets S of \{1, 2, \ldots, N\} such that \displaystyle\sum_{i \in S} A_i is divisible by K.

Note that the sweets are distinguished by their indices. Even if multiple sweets have the same calorie value, they are treated as distinct if their indices are different.

Since the answer can be very large, find the count modulo 998244353.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq K \leq 2 \times 10^5
• N \times K \leq 2 \times 10^7
• 1 \leq A_i \leq 10^9
• All input values are integers.

Sample Input 1

4 3
1 2 3 4

Sample Output 1

5

Sample Input 2

2 5
1 2

Sample Output 2

0

Sample Input 3

12 10
7 13 20 4 16 9 25 30 11 6 18 2

Sample Output 3

411

Sample Input 4

50 60
1 999999937 120 45 78 300 17 2048 999999999 60 61 122 183 244 305 366 427 488 549 610 671 732 793 854 915 976 1037 1098 1159 1220 1281 1342 1403 1464 1525 1586 1647 1708 1769 1830 1891 1952 2013 2074 2135 2196 2257 2318 2379 1000000000

Sample Output 4

1108801

Sample Input 5

1 1
1000000000

Sample Output 5

1

Problem Statement

Takahashi is participating in the "Exact Shopping Challenge" held at a shopping mall.

The rules of this challenge are as follows. There are N items lined up in the venue, numbered from 1 to N, and the price of the i-th item (1 \leq i \leq N) is P_i yen. Takahashi must select and purchase 1 or more of these items, and if the total price of the selected items exactly matches the target amount of S yen, the challenge is successful. However, the same item cannot be selected more than once.

What Takahashi is concerned about as he faces the challenge is how many ways there are to succeed. If there are 0 ways to succeed, the challenge is hopeless. If there is only 1 way, he must find that unique combination precisely, which makes him anxious. If there are 2 or more ways, there is room for trial and error, so he can approach it relatively relaxed.

Here, a "way of selecting" refers to the set of items chosen. Since items are distinguished by their numbers, even if multiple items have the same price, they are treated as different items. If the sets of selected items differ, they are counted as different ways.

Let C be the total number of ways to select items such that the total price is exactly S yen. Output the following according to the value of C:

• When C = 0: NO
• When C = 1: ALMOST
• When C \geq 2: YES

Constraints

• 1 \leq N \leq 40
• 1 \leq S \leq 10^{18}
• 1 \leq P_i \leq 10^{18}
• All inputs are integers

Sample Input 1

4 7
2 3 4 5

Sample Output 1

YES

Sample Input 2

3 10
1 2 4

Sample Output 2

NO

Sample Input 3

12 50
1 2 4 8 16 32 64 128 256 512 1000 2000

Sample Output 3

ALMOST

Sample Input 4

35 1000000000000000000
1000000000000000000 1000000000000000000 600000000000000000 600000000000000001 600000000000000002 600000000000000003 600000000000000004 600000000000000005 600000000000000006 600000000000000007 600000000000000008 600000000000000009 600000000000000010 600000000000000011 600000000000000012 600000000000000013 600000000000000014 600000000000000015 600000000000000016 600000000000000017 600000000000000018 600000000000000019 600000000000000020 600000000000000021 600000000000000022 600000000000000023 600000000000000024 600000000000000025 600000000000000026 600000000000000027 600000000000000028 600000000000000029 600000000000000030 600000000000000031 600000000000000032

Sample Output 4

YES

Sample Input 5

1 1
1

Sample Output 5

ALMOST

Problem Statement

Takahashi and Aoki are playing tag in a building consisting of N rooms. The rooms are numbered from 1 to N, and they are connected by M one-way corridors. The i-th corridor allows passage only in one direction, from room U_i to room V_i. There are no corridors from a room to itself (no self-loops), and there are no multiple corridors with the same start and end points.

Takahashi is the runner (evader), and Aoki is the chaser (it). Both players have complete knowledge of the graph structure and always know each other's current position.

At the start of the game, Takahashi is in room S and Aoki is in room R (S \neq R). Since the two players are in different rooms at the start, no capture occurs, and the first turn begins immediately. Each turn consists of the following steps 1–4. Turns repeat indefinitely unless a capture occurs.

1. Takahashi's action: Takahashi chooses one corridor starting from his current room and moves to the room at its end, or he chooses to stay in his current room. (If there are no corridors starting from his current room, he can only stay.)
2. Capture check: If Takahashi and Aoki are in the same room at this point, Takahashi is captured and the game ends.
3. Aoki's action: If Takahashi has not been captured, Aoki chooses one corridor starting from his current room and moves to the room at its end, or he chooses to stay in his current room. (If there are no corridors starting from his current room, he can only stay.)
4. Capture check: If Takahashi and Aoki are in the same room at this point, Takahashi is captured and the game ends.

If Takahashi is not captured in either step 2 or step 4, the game proceeds to step 1 of the next turn.

When both players act optimally, the result is exactly one of the following two outcomes:

• Captured: No matter what strategy Takahashi uses, Aoki can always capture Takahashi within a finite number of turns.
• Escapes: If Takahashi uses an appropriate strategy, he can avoid being captured forever regardless of how Aoki acts.

You are given Q queries. In the j-th query, you are given Takahashi's initial position S_j and Aoki's initial position R_j. Determine whether Takahashi can escape forever when both players act optimally. Each query is independent.

Constraints

• 2 \leq N \leq 500
• 0 \leq M \leq N(N-1)
• 1 \leq U_i \leq N
• 1 \leq V_i \leq N
• U_i \neq V_i (no self-loops)
• All pairs (U_i, V_i) are distinct (no multiple edges)
• 1 \leq Q \leq 100000
• 1 \leq S_j \leq N
• 1 \leq R_j \leq N
• S_j \neq R_j
• The pair (S_j, R_j) may appear in multiple queries
• All inputs are integers

Sample Input 1

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

Sample Output 1

YES
YES
NO
YES
YES

Sample Input 2

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

Sample Output 2

YES
NO
NO
YES
NO
NO

Sample Input 3

10 18
1 2
2 3
3 1
3 4
4 5
5 6
6 4
2 7
7 8
8 7
8 9
9 10
10 9
5 2
6 10
1 6
10 4
7 3
12
1 4
4 1
7 10
10 7
9 2
6 8
3 5
8 1
2 9
5 10
10 6
4 7

Sample Output 3

YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
YES

Sample Input 4

20 55
1 2
2 3
3 4
4 5
5 1
6 7
7 8
8 9
9 10
10 6
11 12
12 13
13 14
14 15
15 11
16 17
17 18
18 19
19 20
20 16
1 3
2 5
3 1
4 2
5 4
6 8
7 10
8 6
9 7
10 9
11 13
12 15
13 11
14 12
15 14
16 18
17 20
18 16
19 17
20 19
3 6
5 11
10 15
14 20
18 2
7 12
13 8
19 4
1 16
11 6
20 10
15 1
6 14
9 18
2 13
25
1 10
10 1
5 15
15 5
6 13
13 6
20 2
2 20
8 18
18 8
11 16
16 11
3 19
19 3
7 14
14 7
4 12
12 4
9 1
1 9
17 5
5 17
10 20
20 10
6 19

Sample Output 4

YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES

Sample Input 5

2 0
4
1 2
2 1
1 2
2 1

Sample Output 5

YES
YES
YES
YES