Problem Statement

Takahashi and Aoki are playing a stone taking game.

There are N piles of stones on the table, and each pile is numbered from 1 to N. Pile i contains A_i stones.

The game starts with Takahashi, and the two players alternately perform the following operation:

• Choose one pile that still has stones remaining, and remove 1 stone from that pile.
• A pile with 0 stones becomes empty and can no longer be chosen.

When all piles become empty, the player who took the last stone wins.

Determine which player wins when both players play optimally.

Constraints

• 1 \leq N \leq 10^5
• 1 \leq A_i \leq 10^9
• All inputs are integers

Sample Input 1

3
1 2 1

Sample Output 1

Aoki

Sample Input 2

2
3 4

Sample Output 2

Takahashi

Sample Input 3

8
7 1 4 2 6 3 5 8

Sample Output 3

Aoki

Sample Input 4

20
1000000000 999999999 123456789 987654321 500000000 400000000 300000000 200000000 100000000 999999998 7654321 8765432 135791357 246802468 111111111 222222222 333333333 444444444 555555555 666666667

Sample Output 4

Takahashi

Sample Input 5

1
1000000000

Sample Output 5

Aoki

Problem Statement

Takahashi is going to meet up with N friends.

His friends are located on a number line, and the i-th friend is at coordinate X_i (different friends may be at the same coordinate).

Takahashi wants to decide on exactly one meeting place. If he sets the meeting place at an integer coordinate P on the number line, each friend will travel to that location. The sum of all friends' travel distances is called the "total travel distance." That is, the total travel distance is |X_1 - P| + |X_2 - P| + \cdots + |X_N - P|. Note that Takahashi's own travel distance is not included in the total travel distance.

Takahashi wants to minimize the total travel distance by choosing P optimally, in order to reduce the burden on his friends as much as possible.

Find the minimum value of the total travel distance.

Constraints

• 1 \leq N \leq 2 \times 10^5
• -10^9 \leq X_i \leq 10^9
• All inputs are integers.

Sample Input 1

3
1 2 10

Sample Output 1

9

Sample Input 2

4
0 0 5 9

Sample Output 2

14

Sample Input 3

10
-12 4 7 -3 0 9 9 15 -8 2

Sample Output 3

65

Sample Input 4

20
12 -5 30 7 7 -18 42 0 3 3 3 50 -1 9 -15 100 -40 8 21 21

Sample Output 4

363

Sample Input 5

1
-1000000000

Sample Output 5

0

Problem Statement

Takahashi is searching for a point along a straight road where the total strength of received signals is maximized.

The road is represented by a number line, where the direction of increasing coordinates is called right and the direction of decreasing coordinates is called left. There are N radio towers installed along the road, numbered Tower 1, Tower 2, \ldots, Tower N. Tower i is built at coordinate X_i, satisfying X_1 \leq X_2 \leq \cdots \leq X_N (multiple towers may be built at the same coordinate).

The radio waves from Tower i reach a distance of L_i to the left and R_i to the right from the tower's position. That is, it covers the range from coordinate X_i - L_i to coordinate X_i + R_i, inclusive. When within the coverage area of Tower i, the strength of the signal that can be received is C_i.

Takahashi will choose and stand at any single point on the road with an integer coordinate (negative coordinates are also allowed). When Takahashi stands at coordinate p (an integer), the total strength of the signals he can receive is

\displaystyle\sum_{\substack{1 \leq i \leq N \\ X_i - L_i \leq p \leq X_i + R_i}} C_i

That is, it is the sum of signal strengths of all towers whose coverage area includes p. If the chosen point is not within the coverage area of any tower, the total signal strength is 0.

Find the maximum total signal strength Takahashi can receive when he optimally chooses where to stand.

Constraints

• 1 \leq N \leq 10^5
• 0 \leq X_i \leq 10^9
• X_1 \leq X_2 \leq \cdots \leq X_N
• 0 \leq L_i \leq 10^9
• 0 \leq R_i \leq 10^9
• 1 \leq C_i \leq 10^4
• All inputs are integers.

Sample Input 1

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

Sample Output 1

9

Sample Input 2

4
0 0 0 7
0 1 2 3
3 1 0 5
10 0 0 1

Sample Output 2

10

Sample Input 3

8
1 1 0 2
4 2 3 5
6 0 2 4
8 3 1 6
10 5 0 3
10 0 4 7
13 2 2 1
20 10 0 8

Sample Output 3

18

Sample Input 4

15
0 0 5 2
2 1 2 4
4 3 0 6
7 2 5 3
9 0 0 8
12 4 1 5
15 5 5 7
18 3 2 4
18 0 6 9
23 10 0 1
25 2 3 6
30 8 4 5
35 0 0 10
40 7 7 2
50 20 0 8

Sample Output 4

21

Sample Input 5

1
1000000000 1000000000 1000000000 10000

Sample Output 5

10000

Problem Statement

There is a fence consisting of N boards in front of Takahashi's house. The boards are numbered from 1 to N from left to right.

Initially, the color number of every board is 0 (unpainted).

Takahashi will perform M repainting operations in order. In the i-th (1 \leq i \leq M) repainting operation, he overwrites all boards from board L_i to board R_i (inclusive) with color number C_i. Even boards that are already painted will be changed to the new color number C_i.

Determine the final color number of each board after all repainting operations are completed.

Constraints

• 1 \leq N \leq 5 \times 10^5
• 0 \leq M \leq 2 \times 10^5
• 1 \leq L_i \leq R_i \leq N (1 \leq i \leq M)
• 1 \leq C_i \leq 10^9 (1 \leq i \leq M)
• All inputs are integers.

Sample Input 1

5 3
1 3 2
2 5 4
4 4 7

Sample Output 1

2 4 4 7 4

Sample Input 2

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

Sample Output 2

9 3 3 3 3 8

Sample Input 3

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

Sample Output 3

5 4 2 2 1 1 1 9 6 9 7 7

Sample Input 4

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

Sample Output 4

10 10 10 10 11 10 10 10 10 12 12 12 12 12 12 12 12 12 10 10

Sample Input 5

1 0

Sample Output 5

0

Problem Statement

Takahashi lives in a kingdom consisting of N cities. The cities are numbered from 1 to N.

There are several one-way roads between cities, and information about a total of M roads is given. The i-th road (1 \leq i \leq M) is a one-way road from city U_i to city V_i (U_i \neq V_i), and has a non-negative integer W_i called its "magic value". The same ordered pair (U_i, V_i) is never given more than once. That is, for any ordered pair of cities (u, v) (u \neq v), there is at most one one-way road from city u to city v. Note that a road from city u to city v and a road from city v to city u may exist independently. When a road from city u to city v exists, we denote its magic value as W(u, v).

Takahashi wants to start from city 1 and arrive at city N by traversing exactly K roads. More precisely, a sequence of K+1 city numbers v_0, v_1, \ldots, v_K that satisfies all of the following conditions is called a path:

• v_0 = 1
• v_K = N
• For all j = 1, 2, \ldots, K, there exists a road from city v_{j-1} to city v_j

Visiting the same city or traversing the same road multiple times is allowed. Passing through city N along the way (i.e., having N appear among v_1, v_2, \ldots, v_{K-1}) is also allowed.

The total magic of a path v_0, v_1, \ldots, v_K is defined as the product of the magic values of the K roads traversed. That is,

\prod_{j=1}^{K} W(v_{j-1}, v_j)

Takahashi wants to compute the total magic for every possible path and find their sum.

Since this value can be extremely large, find the remainder when divided by 998244353. Here, 998244353 is a prime number. Output the answer as an integer between 0 and 998244352, inclusive.

Constraints

• 2 \leq N \leq 100
• 0 \leq M \leq N(N-1)
• 1 \leq K \leq 10^9
• 1 \leq U_i \leq N
• 1 \leq V_i \leq N
• U_i \neq V_i
• 0 \leq W_i \leq 10^9
• The same ordered pair (U_i, V_i) is never given more than once
• All input values are integers

Sample Input 1

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

Sample Output 1

22

Sample Input 2

3 1 2
1 2 5

Sample Output 2

0

Sample Input 3

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

Sample Output 3

63

Sample Input 4

10 15 1000000000
1 2 100
2 3 200
3 4 300
4 5 400
5 6 500
6 7 600
7 8 700
8 9 800
9 10 900
1 5 10
5 10 20
3 7 50
2 10 1000000000
1 10 999999999
7 10 42

Sample Output 4

0

Sample Input 5

2 0 1

Sample Output 5

0