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

You are given a string S of length N consisting of lowercase English letters.
We denote the i-th character of S by S_i.
Print the string of length 2N obtained by concatenating S_1,S_1,S_2,S_2,\dots,S_N, and S_N in this order.
For example, if S is beginner, print bbeeggiinnnneerr.

Constraints

• N is an integer such that 1 \le N \le 50.
• S is a string of length N consisting of lowercase English letters.

Sample Input 1

8
beginner

Sample Output 1

bbeeggiinnnneerr

It is the same as the example described in the problem statement.

Sample Input 2

3
aaa

Sample Output 2

aaaaaa

Problem Statement

Takahashi is playing a game called Chess960. He has decided to write a code that determines if a random initial state satisfies the conditions of Chess960.

You are given a string S of length eight. S has exactly one K and Q, and exactly two R's, B's , and N's. Determine if S satisfies all of the following conditions.

• Suppose that the x-th and y-th (x < y) characters from the left of S are B; then, x and y have different parities.

• K is between two R's. More formally, suppose that the x-th and y-th (x < y) characters from the left of S are R and the z-th is K; then x< z < y.

Constraints

• S is a string of length 8 that contains exactly one K and Q, and exactly two R's, B's , and N's.

Sample Input 1

RNBQKBNR

Sample Output 1

Yes

The 3-rd and 6-th characters are B, and 3 and 6 have different parities. Also, K is between the two R's. Thus, the conditions are fulfilled.

Sample Input 2

KRRBBNNQ

Sample Output 2

No

K is not between the two R's.

Sample Input 3

BRKRBQNN

Sample Output 3

No

Problem Statement

You are given a string S of length N consisting of lowercase English letters. The x-th (1 \le x \le N) character of S is S_x.

For each i=1,2,\dots,N-1, find the maximum non-negative integer l that satisfies all of the following conditions:

• l+i \le N, and
• for all integers k such that 1 \le k \le l, it holds that S_{k} \neq S_{k+i}.

Note that l=0 always satisfies the conditions.

Constraints

• N is an integer such that 2 \le N \le 5000.
• S is a string of length N consisting of lowercase English letters.

Sample Input 1

6
abcbac

Sample Output 1

5
1
2
0
1

In this input, S= abcbac.

• When i=1, we have S_1 \neq S_2, S_2 \neq S_3, \dots, and S_5 \neq S_6, so the maximum value is l=5.
• When i=2, we have S_1 \neq S_3 but S_2 = S_4, so the maximum value is l=1.
• When i=3, we have S_1 \neq S_4 and S_2 \neq S_5 but S_3 = S_6, so the maximum value is l=2.
• When i=4, we have S_1 = S_5, so the maximum value is l=0.
• When i=5, we have S_1 \neq S_6, so the maximum value is l=1.

Problem Statement

We have N fuses connected in series. The i-th fuse from the left has a length of A_i centimeters and burns at a constant speed of B_i centimeters per second.

Consider igniting this object from left and right ends simultaneously. Find the distance between the position where the two flames will meet and the left end of the object.

Constraints

• 1 \leq N \leq 10^5
• 1 \leq A_i,B_i \leq 1000
• All values in input are integers.

Sample Input 1

3
1 1
2 1
3 1

Sample Output 1

3.000000000000000

The two flames will meet at 3 centimeters from the left end of the object.

Sample Input 2

3
1 3
2 2
3 1

Sample Output 2

3.833333333333333

Sample Input 3

5
3 9
1 2
4 6
1 5
5 3

Sample Output 3

8.916666666666668

Problem Statement

There is a two-dimensional plane. For integers r and c between 1 and 9, there is a pawn at the coordinates (r,c) if the c-th character of S_{r} is #, and nothing if the c-th character of S_{r} is ..

Find the number of squares in this plane with pawns placed at all four vertices.

Constraints

• Each of S_1,\ldots,S_9 is a string of length 9 consisting of # and ..

Sample Input 1

##.......
##.......
.........
.......#.
.....#...
........#
......#..
.........
.........

Sample Output 1

2

The square with vertices (1,1), (1,2), (2,2), and (2,1) have pawns placed at all four vertices.

The square with vertices (4,8), (5,6), (7,7), and (6,9) also have pawns placed at all four vertices.

Thus, the answer is 2.

Sample Input 2

.#.......
#.#......
.#.......
.........
....#.#.#
.........
....#.#.#
........#
.........

Sample Output 2

3

Problem Statement

We have a tree with N vertices numbered 1, 2, \dots, N.
The i-th edge (1 \leq i \leq N - 1) connects Vertex u_i and Vertex v_i and has a weight w_i.

For different vertices u and v, let f(u, v) be the greatest weight of an edge contained in the shortest path from Vertex u to Vertex v.

Find \displaystyle \sum_{i = 1}^{N - 1} \sum_{j = i + 1}^N f(i, j).

Constraints

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

Sample Input 1

3
1 2 10
2 3 20

Sample Output 1

50

We have f(1, 2) = 10, f(2, 3) = 20, and f(1, 3) = 20, so we should print their sum, or 50.

Sample Input 2

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

Sample Output 2

76

Problem Statement

Takahashi has a secret integer sequence a. You know that the length of a is N.

You want to guess the contents of a. He has promised to give you the following Q additional pieces of information.

• The i-th information: the value a_{l_i}+a_{l_i+1}+\cdots+a_{r_i}.

Is it possible to determine the sum of all elements in a, a_1+a_2+\cdots+a_N, if the Q pieces of promised information are given?

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq Q \leq \min(2 \times 10^5,\frac{N(N+1)}{2})
• 1 \leq l_i \leq r_i \leq N
• (l_i,r_i) \neq (l_j,r_j)\ (i \neq j)
• All values in input are integers.

Sample Input 1

3 3
1 2
2 3
2 2

Sample Output 1

Yes

From the first and second information, we can find the value a_1+a_2+a_2+a_3. By subtracting the value of a_2 from it, we can determine the value a_1+a_2+a_3.

Sample Input 2

4 3
1 3
1 2
2 3

Sample Output 2

No

We can determine the sum of the first 3 elements of a, but not the sum of all elements.

Sample Input 3

4 4
1 1
2 2
3 3
1 4

Sample Output 3

Yes

The fourth information directly gives us the sum of all elements.

Problem Statement

There are N cards numbered 1,\ldots,N. Card i has P_i written on the front and Q_i written on the back.
Here, P=(P_1,\ldots,P_N) and Q=(Q_1,\ldots,Q_N) are permutations of (1, 2, \dots, N).

How many ways are there to choose some of the N cards such that the following condition is satisfied? Find the count modulo 998244353.

Condition: every number 1,2,\ldots,N is written on at least one of the chosen cards.

Constraints

• 1 \leq N \leq 2\times 10^5
• 1 \leq P_i,Q_i \leq N
• P and Q are permutations of (1, 2, \dots, N).
• All values in input are integers.

Sample Input 1

3
1 2 3
2 1 3

Sample Output 1

3

For example, if you choose Cards 1 and 3, then 1 is written on the front of Card 1, 2 on the back of Card 1, and 3 on the front of Card 3, so this combination satisfies the condition.

There are 3 ways to choose cards satisfying the condition: \{1,3\},\{2,3\},\{1,2,3\}.

Sample Input 2

5
2 3 5 4 1
4 2 1 3 5

Sample Output 2

12

Sample Input 3

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

Sample Output 3

1