Problem Statement

You are given N-digit positive integers A and B whose topmost digits are not 0.

You can repeat the following operation any number of times (possibly zero).

• Choose an integer i such that 1 \le i \le N and swap the i-th lowest digits of A and B.

Find the smallest possible value of A \times B after your operations, modulo 998244353.

Note that you are not asked to minimize the remainder when A \times B is divided by 998244353.

Constraints

• 1 \le N \le 200000
• A and B are N-digit positive integers whose topmost digits are not 0.

Sample Input 1

2
13
22

Sample Output 1

276

You can make A \times B = 276 by performing the operation once, as follows.

• Choose i=1 to swap the bottommost digits of A and B, making A=12, B=23.

You cannot make A \times B = 275 or less, so the answer is 276.

Sample Input 2

8
20220122
21002300

Sample Output 2

54558365

Find the value modulo 998244353.

Problem Statement

You are given strings S and T of length N consisting of lowercase English letters.

You can repeat the following operation any number of times (possibly zero).

• Erase the first character of S and insert the same character at any position of S.

Determine whether it is possible to make S equal T, and if it is possible, find the minimum number of operations needed.

Constraints

• 1 \le N \le 2 \times 10^5
• S and T are strings of length N consisting of lowercase English letters.

Sample Input 1

4
abab
abba

Sample Output 1

2

You can make S equal T in two operations, as follows.

• Erase the first character of S, and insert that character a at the end of S, making S baba.
• Erase the first character of S, and insert that character b between the 2-nd and 3-rd characters of S, making S abba.

It is impossible to make S equal T in one or fewer operations, so the answer is 2.

Sample Input 2

3
arc
cra

Sample Output 2

2

Problem Statement

You are given sequences of positive integers of length N: A=(A_1,A_2,\dots,A_N) and B=(B_1,B_2,\dots,B_N).

You can repeat the following operation any number of times (possibly zero).

• Choose an integer i such that 1 \le i \le N and replace A_i with A_{i+1}.

Here, regard A_{N+1} as A_1.

Determine whether it is possible to make A equal B.

You have T test cases to solve.

Constraints

• 1 \le T \le 5000
• 1 \le N \le 5000
• 1 \le A_i,B_i \le N
• For each input file, the sum of N over all test cases does not exceed 5000.

Sample Input 1

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

Sample Output 1

Yes
Yes
No

In the first test case, you can make A equal B as follows.

• Choose i=1 to replace A_1 with A_2, making A=(2,2).

In the second test case, you can make A equal B as follows.

• Choose i=4 to replace A_4 with A_1, making A=(2,3,1,2).
• Choose i=2 to replace A_2 with A_3, making A=(2,1,1,2).

In the third test case, there is no way to make A equal B.

Problem Statement

PCT has a permutation (P_1,P_2,\dots,P_N) of (1,2,\dots,N). You are only informed of N.

You can ask him at most 25000 questions of the following form.

• Specify a triple of integers (i,j,k) such that 1 \le i,j,k \le N and ask whether P_i + P_j > P_k.

Find all of P_1,P_2,\dots,P_N.

Constraints

• 1 \le N \le 2000
• P is decided before the start of the interaction of your program and the judge.

Input and Output

This is an interactive task, where your program and the judge interact via input and output.

First, your program is given N, the length of the permutation, from Standard Input:

N

Then, you get to ask questions. Print your question to Standard Output in the following format: (There should be a newline at the end.)

? i j k

If the question is valid, the answer ans will be given from Standard Input:

ans

Here, ans is Yes or No.

If the question is malformed or judged invalid because you have asked more questions than allowed, -1 will be given from Standard Input:

-1

Here, the submission has already been judged incorrect. The judge will end the interaction at this point; preferably, your program should also quit.

Once you have identified all of P_1, P_2, \dots, P_N, print them to Standard Output in the following format: (There should be a newline at the end.)

! P_1 P_2 \dots P_N

Judging

• Each time you print something, end it with a newline and flush Standard Output. Otherwise, you might get a TLE verdict.
• After printing the answer (or receiving -1), immediately terminate the program normally. Otherwise, the verdict will be indeterminate.
• Note that unnecessary newlines will be considered as malformed output.

Sample Interaction

Below is an interaction with N = 4 and P=(3,1,2,4).

Problem Statement

For a permutation Q=(Q_1,Q_2,\dots,Q_N) of (1,2,\dots,N), let f(Q) be the following value:

the sum of j-i over all pairs of integers (i,j) such that 1 \le i < j \le N and Q_i > Q_j.

You are given a permutation P=(P_1,P_2,\dots,P_N) of (1,2,\dots,N).

Let us repeat the following operation M times.

• Choose a pair of integers (i,j) such that 1 \le i \le j \le N. Reverse P_i,P_{i+1},\dots,P_j. Formally, replace the values of P_i,P_{i+1},\dots,P_j with P_j,P_{j-1},\dots,P_i simultaneously.

There are \left(\frac{N(N+1)}{2}\right)^{M} ways to repeat the operation. Assume that we have computed f(P) for all those ways.

Find the sum of these \left(\frac{N(N+1)}{2}\right)^{M} values, modulo 998244353.

Constraints

• 1 \le N,M \le 2 \times 10^5
• (P_1,P_2,\dots,P_N) is a permutation of (1,2,\dots,N).

Sample Input 1

2 1
1 2

Sample Output 1

1

There are three ways to perform the operation, as follows.

• Choose (i,j)=(1,1), making P=(1,2), where f(P)=0.
• Choose (i,j)=(1,2), making P=(2,1), where f(P)=1.
• Choose (i,j)=(2,2), making P=(1,2), where f(P)=0.

Thus, the answer is 0+1+0=1.

Sample Input 2

3 2
3 2 1

Sample Output 2

90

Sample Input 3

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

Sample Output 3

543960046

Problem Statement

We have an N-sided die where all sides have the same probability to show up. Let us repeat rolling this die until every side has shown up.

For integers i such that 1 \le i \le M, find the expected value, modulo 998244353, of the i-th power of the number of times we roll the die.

Constraints

• 1 \le N,M \le 2 \times 10^5
• All values in the input are integers.

Sample Input 1

3 3

Sample Output 1

499122182
37
748683574

For i=1, you should find the expected value of the number of times we roll the die, which is \frac{11}{2}.

Sample Input 2

7 8

Sample Output 2

449209977
705980975
631316005
119321168
62397541
596241562
584585746
378338599

Sample Input 3

2023 7

Sample Output 3

442614988
884066164
757979000
548628857
593993207
780067557
524115712