Problem Statement

One day, Takahashi got up at exactly B minutes past A o'clock (in 24-hour clock), and Aoki got up at exactly D minutes and 1 second past C o'clock.
If Takahashi got up earlier than Aoki, print Takahashi; otherwise, print Aoki.

Constraints

• 0 \leq A \leq 23
• 0 \leq B \leq 59
• 0 \leq C \leq 23
• 0 \leq D \leq 59
• All values in input are integers.

Sample Input 1

7 0 6 30

Sample Output 1

Aoki

Takahashi got up at 7 sharp, and Aoki got up at 30 minutes and 1 second past 6 o'clock. Aoki was the first to get up, so Aoki should be printed.

Sample Input 2

7 30 7 30

Sample Output 2

Takahashi

Takahashi got up at exactly half past 7, and Aoki got up at 30 minutes and 1 second past 7 o'clock. Just by one second, Takahashi was the first to get up, so Takahashi should be printed.

Sample Input 3

0 0 23 59

Sample Output 3

Takahashi

0:00 in a day is one minute before 0:01, not one minute past 23:59 ("24:00"). Thus, Takahashi was the first to get up, so Takahashi should be printed.

Problem Statement

You are given a sequence of length N consisting of integers: A=(A_1,\ldots,A_N).

Find the smallest non-negative integer not in (A_1,\ldots,A_N).

Constraints

• 1 \leq N \leq 2000
• 0 \leq A_i \leq 2000
• All values in input are integers.

Sample Input 1

8
0 3 2 6 2 1 0 0

Sample Output 1

4

The non-negative integers are 0,1,2,3,4,\ldots.
We have 0,1,2,3 in A, but not 4, so the answer is 4.

Sample Input 2

3
2000 2000 2000

Sample Output 2

0

Problem Statement

You are given two sequences, each of length N, consisting of integers: A=(A_1, \ldots, A_N) and B=(B_1, \ldots, B_N).

Determine whether there is a sequence of length N, X=(X_1, \ldots, X_N), satisfying all of the conditions below.

• X_i = A_i or X_i = B_i, for every i(1\leq i\leq N).

• |X_i - X_{i+1}| \leq K, for every i(1\leq i\leq N-1).

Constraints

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

Sample Input 1

5 4
9 8 3 7 2
1 6 2 9 5

Sample Output 1

Yes

X=(9,6,3,7,5) satisfies all conditions.

Sample Input 2

4 90
1 1 1 100
1 2 3 100

Sample Output 2

No

No X satisfies all conditions.

Sample Input 3

4 1000000000
1 1 1000000000 1000000000
1 1000000000 1 1000000000

Sample Output 3

Yes

Problem Statement

We have a polynomial of degree N, A(x)=A_Nx^N+A_{N-1}x^{N-1}+\cdots +A_1x+A_0,
and another of degree M, B(x)=B_Mx^M+B_{M-1}x^{M-1}+\cdots +B_1x+B_0.
Here, each coefficient of A(x) and B(x) is an integer whose absolute value is at most 100, and the leading coefficients are not 0.

Also, let the product of them be C(x)=A(x)B(x)=C_{N+M}x^{N+M}+C_{N+M-1}x^{N+M-1}+\cdots +C_1x+C_0.

Given A_0,A_1,\ldots, A_N and C_0,C_1,\ldots, C_{N+M}, find B_0,B_1,\ldots, B_M.
Here, the given inputs guarantee that there is a unique sequence B_0, B_1, \ldots, B_M that satisfies the given conditions.

Constraints

• 1 \leq N < 100
• 1 \leq M < 100
• |A_i| \leq 100
• |C_i| \leq 10^6
• A_N \neq 0
• C_{N+M} \neq 0
• There is a unique sequence B_0, B_1, \ldots, B_M that satisfies the conditions given in the statement.

Sample Input 1

1 2
2 1
12 14 8 2

Sample Output 1

6 4 2

For A(x)=x+2 and B(x)=2x^2+4x+6, we have C(x)=A(x)B(x)=(x+2)(2x^2+4x+6)=2x^3+8x^2+14x+12, so B(x)=2x^2+4x+6 satisfies the given conditions. Thus, B_0=6, B_1=4, B_2=2 should be printed in this order, with spaces in between.

Sample Input 2

1 1
100 1
10000 0 -1

Sample Output 2

100 -1

We have A(x)=x+100, C(x)=-x^2+10000, for which B(x)=-x+100 satisfies the given conditions. Thus, 100, -1 should be printed in this order, with spaces in between.

Problem Statement

Takahashi has N pieces of chocolate. The i-th piece has a rectangular shape with a width of A_i centimeters and a length of B_i centimeters.
He also has M boxes. The i-th box has a rectangular shape with a width of C_i centimeters and a length of D_i centimeters.

Determine whether it is possible to put the N pieces of chocolate in the boxes under the conditions below.

• A box can contain at most one piece of chocolate.
• A_i \leq C_j and B_i \leq D_j must hold when putting the i-th piece of chocolate in the j-th box (they cannot be rotated).

Constraints

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

Sample Input 1

2 3
2 4
3 2
8 1 5
2 10 5

Sample Output 1

Yes

We can put the first piece of chocolate in the third box and the second piece in the first box.

Sample Input 2

2 2
1 1
2 2
100 1
100 1

Sample Output 2

No

A box can contain at most one piece of chocolate.

Sample Input 3

1 1
10
100
100
10

Sample Output 3

No

Sample Input 4

1 1
10
100
10
100

Sample Output 4

Yes

Problem Statement

We have a simple directed graph G with N vertices and M edges. The vertices are labeled as Vertex 1, Vertex 2, \ldots, Vertex N. The i-th edge (1\leq i\leq M) goes from Vertex U_i to Vertex V_i.

Takahashi will start at a vertex and repeatedly travel on G from one vertex to another along a directed edge. How many vertices of G have the following condition: Takahashi can start at that vertex and continue traveling indefinitely by carefully choosing the path?

Constraints

• 1 \leq N \leq 2\times 10^5
• 0 \leq M \leq \min(N(N-1), 2\times 10^5)
• 1 \leq U_i,V_i\leq N
• U_i\neq V_i
• (U_i,V_i)\neq (U_j,V_j) if i\neq j.
• All values in input are integers.

Sample Input 1

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

Sample Output 1

4

When starting at Vertex 2, Takahashi can continue traveling indefinitely: 2 \to 3 \to 4 \to 2 \to 3 \to \cdots The same goes when starting at Vertex 3 or Vertex 4. From Vertex 1, he can first go to Vertex 2 and then continue traveling indefinitely again.
On the other hand, from Vertex 5, he cannot move at all.

Thus, four vertices ―Vertex 1, 2, 3, and 4― satisfy the conditions, so 4 should be printed.

Sample Input 2

3 2
1 2
2 1

Sample Output 2

2

Note that, in a simple directed graph, there may be two edges in opposite directions between the same pair of vertices. Additionally, G may not be connected.

Problem Statement

There are N people and K nations, labeled as Person 1, Person 2, \ldots, Person N and Nation 1, Nation 2, \ldots, Nation K, respectively.
Each person belongs to exactly one nation: Person i belongs to Nation A_i. Additionally, there are L popular people among them: Person B_1, Person B_2, \ldots, Person B_L are popular. Initially, no two of the N people are friends.

For M pairs of people, Takahashi, a God, can make them friends by paying a certain cost: for each 1\leq i\leq M, he can pay the cost of C_i to make Person U_i and Person V_i friends.

Now, for each 1\leq i\leq N, solve the following problem.

Can Takahashi make Person i an indirect friend of a popular person belonging to a nation different from that of Person i? If he can do so, find the minimum total cost needed. Here, Person s is said to be an indirect friend of Person t when there exists a non-negative integer n and a sequence of people (u_0, u_1, \ldots, u_n) such that u_0=s, u_n=t, and Person u_i and Person u_{i+1} are friends for each 0\leq i < n.

Constraints

• 2 \leq N \leq 10^5
• 1 \leq M \leq 10^5
• 1 \leq K \leq 10^5
• 1 \leq L \leq N
• 1 \leq A_i \leq K
• 1 \leq B_1<B_2<\cdots<B_L\leq N
• 1\leq C_i\leq 10^9
• 1\leq U_i<V_i\leq N
• (U_i, V_i)\neq (U_j,V_j) if i \neq j.
• All values in input are integers.

Sample Input 1

4 4 2 2
1 1 2 2
2 3
1 2 15
2 3 30
3 4 40
1 4 10

Sample Output 1

45 30 30 25

Person 1, 2, 3, 4 belong to Nation 1, 1, 2, 2, respectively, and there are two popular people: Person 2 and 3. Here,

• For Person 1, the only popular person belonging to a different nation is Person 3. To make them indirect friends with the minimum cost, we should pay the cost of 15 to make Person 1 and 2 friends and pay 30 to make Person 2 and 3 friends, for a total of 15+30=45.
• For Person 2, the only popular person belonging to a different nation is Person 3. The minimum cost is achieved by making Person 2 and 3 friends by paying 30.
• For Person 3, the only popular person belonging to a different nation is Person 2. The minimum cost is achieved by making Person 2 and 3 friends by paying 30.
• For Person 4, the only popular person belonging to a different nation is Person 2. To make them indirect friends with the minimum cost, we should pay the cost of 15 to make Person 1 and 2 friends and pay 10 to make Person 1 and 4 friends, for a total of 15+10=25.

Sample Input 2

3 1 3 1
1 2 3
1
1 2 1000000000

Sample Output 2

-1 1000000000 -1

Note that, for Person 1, Person 1 itself is indeed an indirect friend, but it does not belong to a different nation, so there is no popular person belonging to a different nation.

Problem Statement

Among the sequences of length K consisting of integers, A=(A_1, \ldots, A_K), how many satisfy all of the conditions below?
Find the count modulo 998244353.

• 0\leq A_i \leq M-1 for every i(1\leq i\leq K).

• \displaystyle\prod_{i=1}^{K} A_i \equiv N \pmod M.

Constraints

• 1 \leq K \leq 10^9
• 0 \leq N \lt M \leq 10^{12}
• All values in input are integers.

Sample Input 1

2 3 6

Sample Output 1

5

The five sequences A satisfying the conditions are (1,3),(3,1),(3,3),(3,5),(5,3).

Sample Input 2

10 0 2

Sample Output 2

1023

Sample Input 3

1000000000 20220326 1000000000000

Sample Output 3

561382653

Be sure to find the count modulo 998244353.