Problem Statement

You are given an integer N. If N is between -2^{31} and 2^{31}-1 (inclusive), print Yes; otherwise, print No.

Constraints

• -2^{63} \leq N < 2^{63}
• N is an integer.

Sample Input 1

10

Sample Output 1

Yes

10 is between -2^{31} and 2^{31}-1, so Yes should be printed.

Sample Input 2

-9876543210

Sample Output 2

No

-9876543210 is less than -2^{31}, so No should be printed.

Sample Input 3

483597848400000

Sample Output 3

No

483597848400000 is greater than 2^{31}-1, so No should be printed.

Problem Statement

You are given an H-by-W matrix A.
The element at the i-th row from the top and j-th column from the left of A is A_{i,j}.

Let B be a W-by-H matrix whose element at the i-th row from the top and j-th column from the left equals A_{j, i}.
That is, B is the transpose of A.

Print B.

Constraints

• 1\leq H,W \leq 10^5
• H \times W \leq 10^5
• 1 \leq A_{i,j} \leq 10^9
• All values in input are integers.

Sample Input 1

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

Sample Output 1

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

For example, we have A_{2,1}=4, so the element at the 1-st row from the top and 2-nd column from the left of the transpose B is 4.

Sample Input 2

2 2
1000000000 1000000000
1000000000 1000000000

Sample Output 2

1000000000 1000000000
1000000000 1000000000

Problem Statement

Given is a string S consisting of lowercase English letters. Determine whether adding some number of a's (possibly zero) at the beginning of S can make it a palindrome.

Here, a string of length N, A=A_1A_2\ldots A_N, is said to be a palindrome when A_i=A_{N+1-i} for every 1\leq i\leq N.

Constraints

• 1 \leq \lvert S \rvert \leq 10^6
• S consists of lowercase English letters.

Sample Input 1

kasaka

Sample Output 1

Yes

By adding one a at the beginning of kasaka, we have akasaka, which is a palindrome, so Yes should be printed.

Sample Input 2

atcoder

Sample Output 2

No

Adding any number of a's at the beginning of atcoder does not make it a palindrome.

Sample Input 3

php

Sample Output 3

Yes

php itself is a palindrome. Adding zero a's at the beginning of S is allowed, so Yes should be printed.

Problem Statement

There is a sequence that contains one 0, A=(0).
Additionally, you are given a string of length N, S=s_1s_2\ldots s_N, consisting of L and R.

For each i=1, 2, \ldots, N in this order, the following will be done.

• If s_i is L, insert i to the immediate left of i-1 in A.
• If s_i is R, insert i to the immediate right of i-1 in A.

Find the final contents of A.

Constraints

• 1\leq N \leq 5\times 10^5
• N is an integer.
• |S| = N
• s_i is L or R.

Sample Input 1

5
LRRLR

Sample Output 1

1 2 4 5 3 0

Initially, A=(0).
S_1 is L, which makes it A=(1,0).
S_2 is R, which makes it A=(1,2,0).
S_3 is R, which makes it A=(1,2,3,0).
S_4 is L, which makes it A=(1,2,4,3,0).
S_5 is R, which makes it A=(1,2,4,5,3,0).

Sample Input 2

7
LLLLLLL

Sample Output 2

7 6 5 4 3 2 1 0

Problem Statement

AtCoder Ski Area has N open spaces called Space 1, Space 2, \ldots, Space N. The altitude of Space i is H_i. There are M slopes that connect two spaces bidirectionally. The i-th slope (1 \leq i \leq M) connects Space U_i and Space V_i. It is possible to travel between any two spaces using some slopes.

Takahashi can only travel between spaces by using slopes. Each time he goes through a slope, his happiness changes. Specifically, when he goes from Space X to Space Y by using the slope that directly connects them, his happiness changes as follows.

• If the altitude of Space X is strictly higher than that of Space Y, the happiness increases by their difference: H_X-H_Y.
• If the altitude of Space X is strictly lower than that of Space Y, the happiness decreases by their difference multiplied by 2: 2(H_Y-H_X).
• If the altitude of Space X is equal to that of Space Y, the happiness does not change.

The happiness may be a negative value.

Initially, Takahashi is in Space 1, and his happiness is 0. Find his maximum possible happiness after going through any number of slopes (possibly zero), ending in any space.

Constraints

• 2 \leq N \leq 2\times 10^5
• N-1 \leq M \leq \min( 2\times 10^5,\frac{N(N-1)}{2})
• 0 \leq H_i\leq 10^8 (1 \leq i \leq N)
• 1 \leq U_i < V_i \leq N (1 \leq i \leq M)
• (U_i,V_i) \neq (U_j, V_j) if i \neq j.
• All values in input are integers.
• It is possible to travel between any two spaces using some slopes.

Sample Input 1

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

Sample Output 1

3

If Takahashi takes the route Space 1 \to Space 3 \to Space 4, his happiness changes as follows.

• When going from Space 1 (altitude 10) to Space 3 (altitude 12), it decreases by 2\times (12-10)=4 and becomes 0-4=-4.
• When going from Space 3 (altitude 12) to Space 4 (altitude 5), it increases by 12-5=7 and becomes -4+7=3.

If he ends the travel here, the final happiness will be 3, which is the maximum possible value.

Sample Input 2

2 1
0 10
1 2

Sample Output 2

0

His happiness is maximized by not moving at all.

Problem Statement

Find the number of sequences that satisfy all of the conditions below, modulo 998244353.

• The length is N.
• Each of the elements is an integer between 1 and M (inclusive).
• Its longest increasing subsequence has the length of exactly 3.

Notes

A subsequence of a sequence is the result of removing zero or more elements from it and concatenating the remaining elements without changing the order. For example, (10,30) is a subsequence of (10,20,30), while (20,10) is not a subsequence of (10,20,30).

A longest increasing subsequence of a sequence is its strictly increasing subsequence with the greatest length.

Constraints

• 3 \leq N \leq 1000
• 3 \leq M \leq 10
• All values in input are integers.

Sample Input 1

4 5

Sample Output 1

135

One sequence that satisfies the conditions is (3,4,1,5).
On the other hand, (4,4,1,5) do not, because its longest increasing subsequence has the length of 2.

Sample Input 2

3 4

Sample Output 2

4

Sample Input 3

111 3

Sample Output 3

144980434

Find the count modulo 998244353.

Problem Statement

Given is a permutation P=(P_1,P_2,\ldots,P_N) of 1,2,\ldots,N, and an integer X.

Additionally, Q queries are given. The i-th query is represented as a triple of numbers (C_i,L_i,R_i). Each query does the following operation on the permutation P.

• If C_i=1: sort P_{L_i},P_{L_i+1},\ldots,P_{R_i} in ascending order.
• If C_i=2: sort P_{L_i},P_{L_i+1},\ldots,P_{R_i} in descending order.

In the final permutation P after executing all queries in the given order, find i such that P_i=X.

Constraints

• 1 \leq N \leq 2\times 10^5
• 1 \leq Q \leq 2\times 10^5
• 1 \leq X \leq N
• (P_1,P_2,\ldots,P_N) is a permutation of (1,2,\ldots,N).
• 1 \leq C_i \leq 2
• 1 \leq L_i \leq R_i \leq N
• All values in input are integers.

Sample Input 1

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

Sample Output 1

3

Initially, the permutation is P=[1,4,5,2,3]. The queries change it as follows.

• 1-st query sorts the 3-rd through 5-th elements in ascending order, making P=[1,4,2,3,5].
• 2-nd query sorts the 1-st through 3-rd elements in descending order, making P=[4,2,1,3,5].

In the final permutation, we have P_3=1, so 3 should be printed.

Sample Input 2

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

Sample Output 2

7

The final permutation is P=[1,2,6,5,7,4,3].

Problem Statement

We have a string S consisting of lowercase English letters.
Bob just thinks about palindromes every day. He decided to choose some of the substrings of S that are palindromes and tell them to Anna.

Anna gets angry if one of the palindromes told by Bob is a substring of another.

How many palindromes can Bob choose while not making Anna angry?

Notes

A substring of S is the result of deleting zero or more characters from the beginning and the end of S.
For example, ab is a substring of abc, while ac is not a substring of abc.

Constraints

• 1 \leq |S| \leq 200
• S consists of lowercase English letters.

Sample Input 1

ababb

Sample Output 1

3

Three palindromes aba, bab, bb can be chosen.

Sample Input 2

xyz

Sample Output 2

3

Three palindromes x, y, z can be chosen.

Sample Input 3

xxxxxxxxxx

Sample Output 3

1