Problem Statement

Takahashi melted and mixed A grams of gold and B grams of silver (0 \leq A,B,\ 0 \lt A+B) to produce new metal.

What metal did he produce: pure gold, pure silver, or an alloy?

Formally, the product is called as follows.

• Pure gold, if 0 \lt A and B=0.
• Pure silver, if A=0 and 0 \lt B.
• An alloy, if 0 \lt A and 0 \lt B.

Constraints

• 0 \leq A,B \leq 100
• 1 \leq A+B
• All values in input are integers.

Sample Input 1

50 50

Sample Output 1

Alloy

We have 0 \lt A and 0 \lt B, so the product is an alloy.

Sample Input 2

100 0

Sample Output 2

Gold

We have 0 \lt A and B=0, so the product is pure gold.

Sample Input 3

0 100

Sample Output 3

Silver

We have A=0 and 0 \lt B, so the product is pure silver.

Sample Input 4

100 2

Sample Output 4

Alloy

Problem Statement

You are given a 4-digit PIN: X_1X_2X_3X_4, which may begin with a 0. The PIN is said to be weak when it satisfies one of the following conditions:

• All of the four digits are the same.
• For each integer i such that 1\leq i\leq 3, X_{i+1} follows X_i. Here, j+1 follows j for each 0\leq j\leq 8, and 0 follows 9.

If the given PIN is weak, print Weak; otherwise, print Strong.

Constraints

• 0 \leq X_1, X_2, X_3, X_4 \leq 9
• X_1, X_2, X_3, and X_4 are integers.

Sample Input 1

7777

Sample Output 1

Weak

All four digits are 7, satisfying the first condition, so this PIN is weak.

Sample Input 2

0112

Sample Output 2

Strong

The first and second digits differ, and the third digit does not follow the second digit, so neither condition is satisfied.

Sample Input 3

9012

Sample Output 3

Weak

Note that 0 follows 9.

Problem Statement

You are given two sequences: A=(A_1,A_2, \ldots ,A_N) consisting of N positive integers, and B=(B_1, \ldots ,B_M) consisting of M positive integers.

Find the minimum difference of an element of A and an element of B, that is, \displaystyle \min_{ 1\leq i\leq N}\displaystyle\min_{1\leq j\leq M} \lvert A_i-B_j\rvert.

Constraints

• 1 \leq N,M \leq 2\times 10^5
• 1 \leq A_i \leq 10^9
• 1 \leq B_i \leq 10^9
• All values in input are integers.

Sample Input 1

2 2
1 6
4 9

Sample Output 1

2

Here is the difference for each of the four pair of an element of A and an element of B: \lvert 1-4\rvert=3, \lvert 1-9\rvert=8, \lvert 6-4\rvert=2, and \lvert 6-9\rvert=3. We should print the minimum of these values, or 2.

Sample Input 2

1 1
10
10

Sample Output 2

0

Sample Input 3

6 8
82 76 82 82 71 70
17 39 67 2 45 35 22 24

Sample Output 3

3

Problem Statement

Takahashi has many balls, on which nothing is written, and one bag. Initially, the bag is empty. Takahashi will do Q operations, each of which is of one of the following three types.

• Type 1: Write an integer X_i on a blank ball and put it in the bag.
• Type 2: For each ball in the bag, replace the integer written on it with that integer plus X_i.
• Type 3: Pick up the ball with the smallest integer in the bag (if there are multiple such balls, pick up one of them). Record the integer written on this ball and throw it away.

For each 1\leq i\leq Q, you are given the type P_i of the i-th operation and the value of X_i if the operation is of Type 1 or 2. Print the integers recorded in the operations of Type 3 in order.

Constraints

• 1 \leq Q \leq 2\times 10^5
• 1 \leq P_i \leq 3
• 1 \leq X_i \leq 10^9
• All values in input are integers.
• There is one or more i such that P_i=3.
• If P_i=3, the bag contains at least one ball just before the i-th operation.

Sample Input 1

5
1 3
1 5
3
2 2
3

Sample Output 1

3
7

Takahashi will do the following operations.

• Write 3 on a ball and put it in the bag.
• Write 5 on a ball and put it in the bag.
• The bag now contains a ball with 3 and another with 5. Pick up the ball with the smaller of them, or 3. Record 3 and throw it away.
• The bag now contains just a ball with 5. Replace this integer with 5+2=7.
• The bag now contains just a ball with 7. Pick up this ball, record 7, and throw it away.

Therefore, we should print 3 and 7, in the order they are recorded.

Sample Input 2

6
1 1000000000
2 1000000000
2 1000000000
2 1000000000
2 1000000000
3

Sample Output 2

5000000000

Note that the outputs may not fit into a 32-bit integer.

Problem Statement

The Republic of AtCoder has N cities, called City 1, City 2, \ldots, City N. Initially, there was a bidirectional road between every pair of different cities, but M of these roads have become unusable due to deterioration over time. More specifically, for each 1\leq i \leq M, the road connecting City U_i and City V_i has become unusable.

Takahashi will go for a K-day trip that starts and ends in City 1. Formally speaking, a K-day trip that starts and ends in City 1 is a sequence of K+1 cities (A_0, A_1, \ldots, A_K) such that A_0=A_K=1 holds and for each 0\leq i\leq K-1, A_i and A_{i+1} are different and there is still a usable road connecting City A_i and City A_{i+1}.

Print the number of different K-day trips that start and end in City 1, modulo 998244353. Here, two K-day trips (A_0, A_1, \ldots, A_K) and (B_0, B_1, \ldots, B_K) are said to be different when there exists an i such that A_i\neq B_i.

Constraints

• 2 \leq N \leq 5000
• 0 \leq M \leq \min\left( \frac{N(N-1)}{2},5000 \right)
• 2 \leq K \leq 5000
• 1 \leq U_i<V_i \leq N
• All pairs (U_i, V_i) are pairwise distinct.
• All values in input are integers.

Sample Input 1

3 1 4
2 3

Sample Output 1

4

There are four different trips as follows.

• (1,2,1,2,1)
• (1,2,1,3,1)
• (1,3,1,2,1)
• (1,3,1,3,1)

No other trip is valid, so we should print 4.

Sample Input 2

3 3 3
1 2
1 3
2 3

Sample Output 2

0

No road remains usable, so there is no valid trip.

Sample Input 3

5 3 100
1 2
4 5
2 3

Sample Output 3

428417047

Problem Statement

There are N cities numbered 1 through N, and M buses that go between these cities. The i-th bus (1 \leq i \leq M) departs from City A_i at time S_i+0.5 and arrive at City B_i at time T_i+0.5.

Takahashi will travel between these N cities. When he is in City p at time t, he will do the following.

1. If there is a bus that departs from City p not earlier than time t, take the bus that departs the earliest among those buses to get to another city.
2. If there is no such bus, do nothing and stay in City p.

Takahashi repeats doing the above until there is no bus to take. It is guaranteed that all M buses depart at different times, so the bus to take is always uniquely determined. Additionally, the time needed to change buses is negligible.

Here is your task: process Q queries, the i-th (1 \leq i \leq Q) of which is as follows.

• If Takahashi begins his travel in City Y_i at time X_i, in which city or on which bus will he be at time Z_i?

Constraints

• 2 \leq N \leq 10^5
• 1 \leq M \leq 10^5
• 1 \leq Q \leq 10^5
• 1 \leq A_i,B_i \leq N\ (1 \leq i \leq M)
• A_i \neq B_i\ (1 \leq i \leq M)
• 1 \leq S_i \lt T_i \leq 10^9\ (1 \leq i \leq M)
• S_i \neq S_j\ (i \neq j)
• 1 \leq X_i \lt Z_i \leq 10^9\ (1 \leq i \leq Q)
• 1 \leq Y_i \leq N\ (1 \leq i \leq Q)
• All values in input are integers.

Sample Input 1

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

Sample Output 1

2 3
2
3

In the first query, Takahashi will travel as follows.

1. Start in City 1 at time 1.
2. Take the bus that departs from City 1 at time 1.5 and arrives at City 2 at time 3.5.
3. Take the bus that departs from City 2 at time 3.5 and arrives at City 3 at time 5.5.
4. Since no bus departs from City 3 at time 5.5 or later, stay in City 3 (forever).

At time 5, he will be on the bus that departs from City 2 and arrives at City 3. Thus, as specified in the Output section, we should print 2 and 3 with a space between them.

Sample Input 2

8 10 10
4 3 329982133 872113932
6 8 101082040 756263297
4 7 515073851 793074419
8 7 899017043 941751547
5 7 295510441 597348810
7 2 688716395 890599546
6 1 414221915 748470452
6 4 810915860 904512496
3 1 497469654 973509612
4 1 307142272 872178157
374358788 4 509276232
243448834 6 585993193
156350864 4 682491610
131643541 8 836902943
152874385 6 495945159
382276121 1 481368090
552433623 2 884584430
580376205 2 639442239
108790644 7 879874292
883275610 1 994982498

Sample Output 2

4
6 1
4 1
8
6 1
1
2
2
7 2
1

Problem Statement

Given is a prime number P.

How many pairs of integers (x, y) satisfy the following conditions?

• 0 \leq x \leq P-1
• 0 \leq y \leq P-1
• There exists a positive integer n such that x^n \equiv y \pmod{P}.

Since the answer may be enormous, print it modulo 998244353.

Constraints

• 2 \leq P \leq 10^{12}
• P is a prime number.

Sample Input 1

3

Sample Output 1

4

Four pairs (x, y) = (0, 0), (1, 1), (2, 1), (2, 2) satisfy the conditions.

Sample Input 2

11

Sample Output 2

64

Sample Input 3

998244353

Sample Output 3

329133417

Problem Statement

Given are positive integers N, K, and a sequence of K integers (A_1, A_2, \ldots, A_K).

Takahashi and Aoki will play a game with stones. Initially, there are some heaps of stones, each of which contains one or more stones. The players take turns doing the following operation, with Takahashi going first.

• Choose a heap with one or more stones remaining. Remove any number of stones between 1 and X (inclusive) from that heap, where X is the number of stones remaining.

The player who first gets unable to do the operation loses.

Now, consider the initial arrangements of stones satisfying the following.

• 1\leq M\leq N holds, where M is the number of heaps of stones.
• The number of stones in each heap is one of the following: A_1, A_2, \ldots, A_K.

Assuming that the heaps are ordered, there are K+K^2+\cdots +K^N such initial arrangements of stones. Among them, find the number, modulo 998244353, of arrangements that lead to Takahashi's win, assuming that both players play optimally.

Constraints

• 1 \leq N \leq 2\times 10^5
• 1 \leq K < 2^{16}
• 1 \leq A_i < 2^{16}
• All A_i are distinct.
• All values in input are integers.

Sample Input 1

2 2
1 2

Sample Output 1

4

There are six possible initial arrangements of stones: (1), (2), (1,1), (1,2), (2,1), and (2,2).
Takahashi has a winning strategy for four of them: (1), (2), (1,2), and (2,1), and Aoki has a winning strategy for the other two. Thus, we should print 4.

Sample Input 2

100 3
3 5 7

Sample Output 2

112184936

Be sure to find the count modulo 998244353.