Problem Statement

There is a rectangle in the xy-plane. Each edge of this rectangle is parallel to the x- or y-axis, and its area is not zero.

Given the coordinates of three of the four vertices of this rectangle, (x_1, y_1), (x_2, y_2), and (x_3, y_3), find the coordinates of the other vertex.

Constraints

• -100 \leq x_i, y_i \leq 100
• There uniquely exists a rectangle with all of (x_1, y_1), (x_2, y_2), (x_3, y_3) as vertices, edges parallel to the x- or y-axis, and a non-zero area.
• All values in input are integers.

Sample Input 1

-1 -1
-1 2
3 2

Sample Output 1

3 -1

The other vertex of the rectangle with vertices (-1, -1), (-1, 2), (3, 2) is (3, -1).

Sample Input 2

-60 -40
-60 -80
-20 -80

Sample Output 2

-20 -40

Problem Statement

From the point (0,0) in a two-dimensional plane, let us move the distance of 1 toward the point (A, B). Find our coordinates after the move.

Here, after moving the distance of d from a point X to a point Y (d \le length of the segment XY), we are at the point on the segment XY whose distance from X is d.
The Constraints guarantee that the distance between the points (0, 0) and (A, B) is at least 1.

Constraints

• All values in input are integers.
• 0 \le A,B \le 1000
• (A,B) \neq (0,0)

Sample Input 1

3 4

Sample Output 1

0.600000000000 0.800000000000

Printing 0.5999999999 0.8000000001, for example, would also be accepted.

Sample Input 2

1 0

Sample Output 2

1.000000000000 0.000000000000

We may arrive at (A, B).

Sample Input 3

246 402

Sample Output 3

0.521964870245 0.852966983083

Problem Statement

There are N items in a shop. For each i = 1, 2, \ldots, N, the price of the i-th item is A_i yen (the currency of Japan).

Takahashi has K coupons.
Each coupon can be used on one item. You can use any number of coupons, possibly zero, on the same item. Using k coupons on an item with a price of a yen allows you to buy it for \max\lbrace a - kX, 0\rbrace yen.

Print the minimum amount of money Takahashi needs to buy all the items.

Constraints

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

Sample Input 1

5 4 7
8 3 10 5 13

Sample Output 1

12

By using 1 coupon on the 1-st item, 1 coupon on the 3-rd item, and 2 coupons on the 5-th item, Takahashi can:

• buy the 1-st item for \max\lbrace A_1-X, 0 \rbrace = 1 yen,
• buy the 2-nd item for \max\lbrace A_2, 0 \rbrace = 3 yen,
• buy the 3-rd item for \max\lbrace A_3-X, 0 \rbrace = 3 yen,
• buy the 4-th item for \max\lbrace A_4, 0 \rbrace = 5 yen,
• buy the 5-th item for \max\lbrace A_5-2X, 0 \rbrace = 0 yen,

for a total of 1 + 3 + 3 + 5 + 0 = 12 yen, which is the minimum possible.

Sample Input 2

5 100 7
8 3 10 5 13

Sample Output 2

0

Sample Input 3

20 815 60
2066 3193 2325 4030 3725 1669 1969 763 1653 159 5311 5341 4671 2374 4513 285 810 742 2981 202

Sample Output 3

112

Problem Statement

Given an integer N, find the smallest integer X that satisfies all of the conditions below.

• X is greater than or equal to N.
• There is a pair of non-negative integers (a, b) such that X=a^3+a^2b+ab^2+b^3.

Constraints

• N is an integer.
• 0 \le N \le 10^{18}

Sample Input 1

9

Sample Output 1

15

For any integer X such that 9 \le X \le 14, there is no (a, b) that satisfies the condition in the statement.
For X=15, (a,b)=(2,1) satisfies the condition.

Sample Input 2

0

Sample Output 2

0

N itself may satisfy the condition.

Sample Input 3

999999999989449206

Sample Output 3

1000000000000000000

Input and output may not fit into a 32-bit integer type.

Problem Statement

We have an N \times N chessboard. Let (i, j) denote the square at the i-th row from the top and j-th column from the left of this board.
The board is described by N strings S_i.
The j-th character of the string S_i, S_{i,j}, means the following.

• If S_{i,j}= ., the square (i, j) is empty.
• If S_{i,j}= #, the square (i, j) is occupied by a white pawn, which cannot be moved or removed.

We have put a white bishop on the square (A_x, A_y).
Find the minimum number of moves needed to move this bishop from (A_x, A_y) to (B_x, B_y) according to the rules of chess (see Notes).
If it cannot be moved to (B_x, B_y), report -1 instead.

Notes

A white bishop on the square (i, j) can go to the following positions in one move.

• For each positive integer d, it can go to (i+d,j+d) if all of the conditions are satisfied.

  • The square (i+d,j+d) exists in the board.
  • For every positive integer l \le d, (i+l,j+l) is not occupied by a white pawn.

• For each positive integer d, it can go to (i+d,j-d) if all of the conditions are satisfied.

  • The square (i+d,j-d) exists in the board.
  • For every positive integer l \le d, (i+l,j-l) is not occupied by a white pawn.

• For each positive integer d, it can go to (i-d,j+d) if all of the conditions are satisfied.

  • The square (i-d,j+d) exists in the board.
  • For every positive integer l \le d, (i-l,j+l) is not occupied by a white pawn.

• For each positive integer d, it can go to (i-d,j-d) if all of the conditions are satisfied.

  • The square (i-d,j-d) exists in the board.
  • For every positive integer l \le d, (i-l,j-l) is not occupied by a white pawn.

Constraints

• 2 \le N \le 1500
• 1 \le A_x,A_y \le N
• 1 \le B_x,B_y \le N
• (A_x,A_y) \neq (B_x,B_y)
• S_i is a string of length N consisting of . and #.
• S_{A_x,A_y}= .
• S_{B_x,B_y}= .

Sample Input 1

5
1 3
3 5
....#
...#.
.....
.#...
#....

Sample Output 1

3

We can move the bishop from (1,3) to (3,5) in three moves as follows, but not in two or fewer moves.

• (1,3) \rightarrow (2,2) \rightarrow (4,4) \rightarrow (3,5)

Sample Input 2

4
3 2
4 2
....
....
....
....

Sample Output 2

-1

There is no way to move the bishop from (3,2) to (4,2).

Sample Input 3

18
18 1
1 18
..................
.####.............
.#..#..####.......
.####..#..#..####.
.#..#..###...#....
.#..#..#..#..#....
.......####..#....
.............####.
..................
..................
.####.............
....#..#..#.......
.####..#..#..####.
.#.....####..#....
.####.....#..####.
..........#..#..#.
.............####.
..................

Sample Output 3

9

Problem Statement

We have a typewriter with N rows. The keys in the i-th row from the top can type the characters in a string S_i.

Let us use this keyboard to enter a string, as follows.

• First, choose an integer 1 \le k \le N.
• Then, start with an empty string and only use the keys in the k-th row from the top to enter a string of length exactly L.

How many strings of length L can be entered in this way? Since the answer can be enormous, print it modulo 998244353.

Constraints

• N and L are integers.
• 1 \le N \le 18
• 1 \le L \le 10^9
• S_i is a (not necessarily contiguous) non-empty subsequence of abcdefghijklmnopqrstuvwxyz.

Sample Input 1

2 2
ab
ac

Sample Output 1

7

We can enter seven strings: aa, ab, ac, ba, bb, ca, cc.

Sample Input 2

4 3
abcdefg
hijklmnop
qrstuv
wxyz

Sample Output 2

1352

Sample Input 3

5 1000000000
abc
acde
cefg
abcfh
dghi

Sample Output 3

346462871

Be sure to print the answer modulo 998244353.

Problem Statement

There is a rooted tree with N vertices, Vertex 1 being the root. For each i = 1, 2, \ldots, N-1, the i-th edge connects Vertex u_i and Vertex v_i. Each vertex other than the root has a positive integer written on it: for each i = 2, 3, \ldots, N, the integer written on Vertex i is A_i. Takahashi and Aoki will use this rooted tree and a piece to play the following game against each other.

The piece starts on Vertex 1. Until the game ends, they repeat the following procedure.

1. First, Aoki chooses a non-root vertex and replaces the integer written on that vertex with 0.
2. Next, Takahashi moves the piece to a (direct) child of the vertex the piece is on.
3. Then, the game ends if the piece is on a leaf. Even if that is not the case, Takahashi can choose to end the game immediately.

At the end of the game, Takahashi's score will be the integer written at that time on the vertex the piece is on. Takahashi wants to make his score as large as possible, while Aoki wants to make it as small as possible. Print the score Takahashi will get when both players play optimally for their respective purposes.

Constraints

• 2 \leq N \leq 2 \times 10^5
• 1 \leq A_i \leq 10^9
• 1 \leq u_i, v_i \leq N
• The given graph is a tree.
• All values in input are integers.

Sample Input 1

7
2 4 6 5 6 10
1 2
1 3
2 4
2 5
5 6
5 7

Sample Output 1

5

Here is a possible progression of the game when both players play optimally.

1. The piece starts on Vertex 1.
2. Aoki changes the integer written on Vertex 7 from 10 to 0.
3. Takahashi moves the piece from Vertex 1 to Vertex 2.
4. Aoki changes the integer written on Vertex 4 from 6 to 0.
5. Takahashi moves the piece from Vertex 2 to Vertex 5.
6. Takahashi chooses to end the game.

At the end of the game, the piece is on Vertex 5, on which the integer 5 is written at that time, so Takahashi's score will be 5.

Sample Input 2

30
29 27 79 27 30 4 93 89 44 88 70 75 96 3 78 39 97 12 53 62 32 38 84 49 93 53 26 13 25
13 15
14 22
17 24
12 3
4 3
5 8
26 15
3 2
2 9
4 25
4 13
2 10
28 15
6 4
2 5
19 9
2 7
2 14
23 30
17 2
7 16
21 13
13 23
13 20
1 2
6 18
27 6
21 29
11 8

Sample Output 2

70

Problem Statement

You are given a string S of length N consisting of 0, 1, and ?.

You are also given Q queries (x_1, c_1), (x_2, c_2), \ldots, (x_Q, c_Q).
For each i = 1, 2, \ldots, Q, x_i is an integer satisfying 1 \leq x_i \leq N and c_i is one of the characters 0 , 1, and ?.

For i = 1, 2, \ldots, Q in this order, do the following process for the query (x_i, c_i).

1. First, change the x_i-th character from the beginning of S to c_i.
2. Then, print the number of non-empty strings, modulo 998244353, that can be obtained as a (not necessarily contiguous) subsequence of S after replacing each occurrence of ? in S with 0 or 1 independently.

Constraints

• 1 \leq N, Q \leq 10^5
• N and Q are integers.
• S is a string of length N consisting of 0, 1, and ?.
• 1 \leq x_i \leq N
• c_i is one of the characters 0 , 1, and ?.

Sample Input 1

3 3
100
2 1
2 ?
3 ?

Sample Output 1

5
7
10

• The 1-st query starts by changing S to 110. Five strings can be obtained as a subsequence of S = 110: 0, 1, 10, 11, 110. Thus, the 1-st query should be answered by 5.

• The 2-nd query starts by changing S to 1?0. Two strings can be obtained by the ? in S = 1?0: 100 and 110. Seven strings can be obtained as a subsequence of one of these strings: 0, 1, 00, 10, 11, 100, 110. Thus, the 2-nd query should be answered by 7.

• The 3-rd query starts by changing S to 1??. Four strings can be obtained by the ?'s in S = 1??: 100, 101, 110, 111. Ten strings can be obtained as a subsequence of one of these strings: 0, 1, 00, 01, 10, 11, 100, 101, 110, 111. Thus, the 3-rd query should be answered by 10.

Sample Input 2

40 10
011?0??001??10?0??0?0?1?11?1?00?11??0?01
5 0
2 ?
30 ?
7 1
11 1
3 1
25 1
40 0
12 1
18 1

Sample Output 2

746884092
532460539
299568633
541985786
217532539
217532539
217532539
573323772
483176957
236273405

Be sure to print the count modulo 998244353.