Problem Statement

There are N students in Takahashi's class besides Takahashi himself. In a recent test, Takahashi scored X points. The i-th student (1 \leq i \leq N) scored A_i points.

Takahashi feels frustrated when he sees a student who scored higher than him. For each student i, the frustration Takahashi feels is A_i - X if A_i > X, and 0 otherwise.

Find the total frustration Takahashi feels toward all N students.

Constraints

• 1 \leq N \leq 5 \times 10^5
• 0 \leq X \leq 100
• 0 \leq A_i \leq 100
• All inputs are integers

Sample Input 1

5 60
55 60 61 80 40

Sample Output 1

21

Sample Input 2

4 100
99 100 80 0

Sample Output 2

0

Sample Input 3

12 48
30 48 49 50 10 100 47 48 51 52 0 75

Sample Output 3

89

Sample Input 4

30 73
70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99

Sample Output 4

351

Sample Input 5

1 0
100

Sample Output 5

100

Problem Statement

Takahashi is trying to divide N students into two teams: the Red team and the White team. He conducted a survey in advance, asking each student to write their preferred team on a piece of paper.

However, coffee was spilled on some of the survey papers, making several responses unreadable. The unreadable responses are recorded as ?, and it is impossible to determine whether they originally said "Red" or "White".

Each student's response is represented by a single character: R (prefers Red team), W (prefers White team), or ? (unreadable).

Takahashi wants to independently replace each unreadable response (?) with either R (prefers Red team) or W (prefers White team) so as to minimize the absolute difference between the final number of Red team supporters and White team supporters.

Find the minimum possible absolute difference between the number of Red team supporters and the number of White team supporters when the ?s are replaced optimally. If there are no ?s, simply compute the absolute difference based on the responses as they are.

Constraints

• 1 \leq N \leq 10^5
• S_i is one of R, W, or ? (1 \leq i \leq N)

Sample Input 1

5
R
W
?
R
?

Sample Output 1

1

Sample Input 2

8
R
W
?
R
?
?
R
?

Sample Output 2

0

Sample Input 3

10
R
R
W
?
R
?
R
R
?
W

Sample Output 3

0

Problem Statement

Takahashi is in charge of directing a fireworks festival. At the venue, N firework launchers are installed, each launching fireworks at regular intervals.

The launch interval of each launcher i (1 \leq i \leq N) is T_i seconds. However, T_i is not necessarily an integer and is given as a positive rational number. Specifically, each T_i is given as an irreducible fraction \frac{P_i}{Q_i} (P_i, Q_i are positive integers, \gcd(P_i, Q_i) = 1).

All launchers start simultaneously at time 0 and also launch fireworks at time 0. That is, launcher i launches fireworks at times 0, T_i, 2T_i, 3T_i, \ldots.

For the finale, Takahashi wants to know the earliest time after time 0 at which all launchers simultaneously launch fireworks.

Here, the least common multiple of a set of positive rational numbers T_1, T_2, \ldots, T_N is defined as follows. A positive rational number L is called a common multiple of T_1, T_2, \ldots, T_N if \frac{L}{T_i} is a positive integer for all i (1 \leq i \leq N). Common multiples always exist (for example, an appropriate positive integer multiple of T_1 \times T_2 \times \cdots \times T_N is a common multiple), and the smallest among all common multiples is called the least common multiple. This is a natural extension of the least common multiple for integers.

The desired time equals the least common multiple L of T_1, T_2, \ldots, T_N. Find L as an irreducible fraction.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq P_i \leq 10^9
• 1 \leq Q_i \leq 10^9
• \gcd(P_i, Q_i) = 1
• All values given in the input are integers.
• It is guaranteed that when the answer is expressed as an irreducible fraction \frac{A}{B} (A, B are positive integers, \gcd(A, B) = 1), A \leq 10^{18} and B \leq 10^{18}.

Sample Input 1

2
1 2
1 3

Sample Output 1

1 1

Sample Input 2

3
2 3
4 9
8 27

Sample Output 2

8 3

Sample Input 3

5
3 4
5 6
7 3
2 9
1 2

Sample Output 3

210 1

Sample Input 4

8
12 5
18 7
15 4
20 3
14 9
25 6
21 8
10 11

Sample Output 4

6300 1

Sample Input 5

1
999999937 1

Sample Output 5

999999937 1

Problem Statement

Takahashi has N cards. The i-th card (1 \leq i \leq N) has a positive integer P_i written on its front side and a positive integer Q_i written on its back side.

Takahashi wants to select 2 or more cards from among these cards. Let S (S \subseteq \{1, 2, \ldots, N\}, |S| \geq 2) be the set of indices of the selected cards. Determine whether there exists such an S where the product of the integers written on the front sides of the selected cards equals the product of the integers written on the back sides, that is,

\prod_{i \in S} P_i = \prod_{i \in S} Q_i

If such an S exists, output the minimum value of |S| among all S satisfying the condition. If no such S exists, output -1.

Constraints

• 2 \leq N \leq 22
• 1 \leq P_i \leq 100
• 1 \leq Q_i \leq 100
• All input values are integers.

Sample Input 1

3
2 3
3 2
5 5

Sample Output 1

2

Sample Input 2

3
2 1
4 1
8 1

Sample Output 2

-1

Sample Input 3

8
2 3
3 5
5 2
7 1
11 1
13 1
17 1
19 1

Sample Output 3

3

Sample Input 4

15
2 3
3 5
5 7
7 2
11 1
13 1
17 1
19 1
23 1
29 1
31 1
37 1
41 1
43 1
47 1

Sample Output 4

4

Sample Input 5

2
5 5
3 3

Sample Output 5

2

Problem Statement

Takahashi's company has N terminals numbered from 1 to N.

Terminal i (1 \leq i \leq N) displays a single digit D_i (between 0 and 9 inclusive) and has a destination terminal number P_i (1 \leq P_i \leq N) configured.

Takahashi starts from a specified starting terminal and repeats the following operation exactly K times.

1. Record the digit displayed on the current terminal.
2. If the current terminal number is i, move to terminal P_i.

The same terminal may be visited multiple times.

Let d_1, d_2, \ldots, d_K be the digits recorded in order over the K operations. The resulting value V is defined as follows:

V = \sum_{t=1}^{K} d_t \cdot 10^{K-t}

This is the value obtained by interpreting the digit string d_1 d_2 \ldots d_K as a non-negative integer in base 10 (leading zeros are allowed).

When K = 0 (no operations are performed), V = 0.

You are given Q queries. In the j-th query (1 \leq j \leq Q), a starting terminal number S_j and a number of operations K_j are specified. Find the remainder when V, obtained by starting from terminal S_j and performing K_j operations, is divided by M.

Constraints

• 1 \leq N \leq 10^5
• 1 \leq Q \leq 10^5
• N + Q \leq 1.5 \times 10^5
• 1 \leq M \leq 10^9
• 0 \leq D_i \leq 9
• 1 \leq P_i \leq N
• 1 \leq S_j \leq N
• 0 \leq K_j \leq 10^{18}
• All input values are integers.

Sample Input 1

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

Sample Output 1

123
423
234
0

Sample Input 2

3 5 13
0 2
5 2
9 1
1 1
1 3
3 2
2 4
3 0

Sample Output 2

0
3
12
4
0

Sample Input 3

9 8 257
6 2
2 3
0 4
7 2
5 3
1 5
9 8
3 9
4 7
1 4
1 10
6 6
5 0
7 5
8 12
9 1
3 100

Sample Output 3

39
58
118
0
202
176
4
110

Sample Input 4

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

Sample Output 4

814159
175840913
624159159
3782
327335048
95013
215912785
0
482487648
6136136
591984774
1

Sample Input 5

1 4 1
7 1
1 0
1 1
1 10
1 1000000000000000000

Sample Output 5

0
0
0
0