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

You are given a sequence A=(A_0,A_1,\dots,A_{63}) of length 64 consisting of 0 and 1.

Find A_0 2^0 + A_1 2^1 + \dots + A_{63} 2^{63}.

Constraints

• A_i is 0 or 1.

Sample Input 1

1 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

Sample Output 1

13

A_0 2^0 + A_1 2^1 + \dots + A_{63} 2^{63} = 2^0 + 2^2 + 2^3 = 13.

Sample Input 2

1 0 1 0 1 0 0 0 0 1 0 0 1 1 0 1 1 1 1 0 0 0 1 0 0 1 1 1 1 1 1 0 0 0 0 1 0 1 0 1 0 1 1 1 1 0 0 1 1 0 0 0 0 1 0 1 0 1 0 1 0 0 0 0

Sample Output 2

766067858140017173

Problem Statement

You are given a sequence A=(A_1,A_2,\dots,A_{3N}) of length 3N where each of 1,2,\dots, and N occurs exactly three times.

For i=1,2,\dots,N, let f(i) be the index of the middle occurrence of i in A. Sort 1,2,\dots,N in ascending order of f(i).

Formally, f(i) is defined as follows.

• Suppose that those j such that A_j = i are j=\alpha,\beta,\gamma\ (\alpha < \beta < \gamma). Then, f(i) = \beta.

Constraints

• 1\leq N \leq 10^5
• 1 \leq A_j \leq N
• i occurs in A exactly three times, for each i=1,2,\dots,N.
• All input values are integers.

Sample Input 1

3
1 1 3 2 3 2 2 3 1

Sample Output 1

1 3 2

• 1 occurs in A at A_1,A_2,A_9, so f(1) = 2.
• 2 occurs in A at A_4,A_6,A_7, so f(2) = 6.
• 3 occurs in A at A_3,A_5,A_8, so f(3) = 5.

Thus, f(1) < f(3) < f(2), so 1,3, and 2 should be printed in this order.

Sample Input 2

1
1 1 1

Sample Output 2

1

Sample Input 3

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

Sample Output 3

3 4 1 2

Problem Statement

Takahashi has decided to enjoy a wired full-course meal consisting of N courses in a restaurant.
The i-th course is:

• if X_i=0, an antidotal course with a tastiness of Y_i;
• if X_i=1, a poisonous course with a tastiness of Y_i.

When Takahashi eats a course, his state changes as follows:

• Initially, Takahashi has a healthy stomach.
• When he has a healthy stomach,
  • if he eats an antidotal course, his stomach remains healthy;
  • if he eats a poisonous course, he gets an upset stomach.
• When he has an upset stomach,
  • if he eats an antidotal course, his stomach becomes healthy;
  • if he eats a poisonous course, he dies.

The meal progresses as follows.

• Repeat the following process for i = 1, \ldots, N in this order.
  • First, the i-th course is served to Takahashi.
  • Next, he chooses whether to "eat" or "skip" the course.
    • If he chooses to "eat" it, he eats the i-th course. His state also changes depending on the course he eats.
    • If he chooses to "skip" it, he does not eat the i-th course. This course cannot be served later or kept somehow.
  • Finally, (if his state changes, after the change) if he is not dead,
    • if i \neq N, he proceeds to the next course.
    • if i = N, he makes it out of the restaurant alive.

An important meeting awaits him, so he must make it out of there alive.
Find the maximum possible sum of tastiness of the courses that he eats (or 0 if he eats nothing) when he decides whether to "eat" or "skip" the courses under that condition.

Constraints

• All input values are integers.
• 1 \le N \le 3 \times 10^5
• X_i \in \{0,1\}
  • In other words, X_i is either 0 or 1.
• -10^9 \le Y_i \le 10^9

Sample Input 1

5
1 100
1 300
0 -200
1 500
1 300

Sample Output 1

600

The following choices result in a total tastiness of the courses that he eats amounting to 600, which is the maximum possible.

• He skips the 1-st course. He now has a healthy stomach.
• He eats the 2-nd course. He now has an upset stomach, and the total tastiness of the courses that he eats amounts to 300.
• He eats the 3-rd course. He now has a healthy stomach again, and the total tastiness of the courses that he eats amounts to 100.
• He eats the 4-th course. He now has an upset stomach, and the total tastiness of the courses that he eats amounts to 600.
• He skips the 5-th course. He now has an upset stomach.
• In the end, he is not dead, so he makes it out of the restaurant alive.

Sample Input 2

4
0 -1
1 -2
0 -3
1 -4

Sample Output 2

0

For this input, it is optimal to eat nothing, in which case the answer is 0.

Sample Input 3

15
1 900000000
0 600000000
1 -300000000
0 -700000000
1 200000000
1 300000000
0 -600000000
1 -900000000
1 600000000
1 -100000000
1 -400000000
0 900000000
0 200000000
1 -500000000
1 900000000

Sample Output 3

4100000000

The answer may not fit into a 32-bit integer type.

Problem Statement

We have a sequence A=(A_1,A_2,\dots,A_N) of length N. Initially, all the terms are 0.
Using an integer K given in the input, we define a function f(A) as follows:

• Let B be the sequence obtained by sorting A in descending order (so that it becomes monotonically non-increasing).
• Then, let f(A)=B_1 + B_2 + \dots + B_K.

We consider applying Q updates on this sequence.
Apply the following operation on the sequence A for i=1,2,\dots,Q in this order, and print the value f(A) at that point after each update.

• Change A_{X_i} to Y_i.

Constraints

• All input values are integers.
• 1 \le K \le N \le 5 \times 10^5
• 1 \le Q \le 5 \times 10^5
• 1 \le X_i \le N
• 0 \le Y_i \le 10^9

Sample Input 1

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

Sample Output 1

5
6
8
8
15
13
13
11
1
0

In this input, N=4 and K=2. Q=10 updates are applied.

• The 1-st update makes A=(5, 0,0,0). Now, f(A)=5.
• The 2-nd update makes A=(5, 1,0,0). Now, f(A)=6.
• The 3-rd update makes A=(5, 1,3,0). Now, f(A)=8.
• The 4-th update makes A=(5, 1,3,2). Now, f(A)=8.
• The 5-th update makes A=(5,10,3,2). Now, f(A)=15.
• The 6-th update makes A=(0,10,3,2). Now, f(A)=13.
• The 7-th update makes A=(0,10,3,0). Now, f(A)=13.
• The 8-th update makes A=(0,10,1,0). Now, f(A)=11.
• The 9-th update makes A=(0, 0,1,0). Now, f(A)=1.
• The 10-th update makes A=(0, 0,0,0). Now, f(A)=0.

Problem Statement

For two sets of integers, A and B, such that A \cap B = \emptyset, we define f(A,B) as follows.

• Let C=(C_1,C_2,\dots,C_{|A|+|B|}) be a sequence consisting of the elements of A \cup B, sorted in ascending order.
• Take k_1,k_2,\dots,k_{|A|} such that A=\lbrace C_{k_1},C_{k_2},\dots,C_{k_{|A|}}\rbrace. Then, let \displaystyle f(A,B)=\sum_{i=1}^{|A|} k_i.

For example, if A=\lbrace 1,3\rbrace and B=\lbrace 2,8\rbrace, then C=(1,2,3,8), so A=\lbrace C_1,C_3\rbrace; thus, f(A,B)=1+3=4.

We have N sets of integers, S_1,S_2\dots,S_N, each of which has M elements. For each i\ (1 \leq i \leq N), S_i = \lbrace A_{i,1},A_{i,2},\dots,A_{i,M}\rbrace. Here, it is guaranteed that S_i \cap S_j = \emptyset\ (i \neq j).

Find \displaystyle \sum_{1\leq i<j \leq N} f(S_i, S_j).

Constraints

• 1\leq N \leq 10^4
• 1\leq M \leq 10^2
• 1\leq A_{i,j} \leq 10^9
• If i_1 \neq i_2 or j_1 \neq j_2, then A_{i_1,j_1} \neq A_{i_2,j_2}.
• All input values are integers.

Sample Input 1

3 2
1 3
2 8
4 6

Sample Output 1

12

S_1 and S_2 respectively coincide with A and B exemplified in the problem statement, and f(S_1,S_2)=1+3=4. Since f(S_1,S_3)=1+2=3 and f(S_2,S_3)=1+4=5, the answer is 4+3+5=12.

Sample Input 2

1 1
306

Sample Output 2

0

Sample Input 3

4 4
155374934 164163676 576823355 954291757
797829355 404011431 353195922 138996221
191890310 782177068 818008580 384836991
160449218 545531545 840594328 501899080

Sample Output 3

102

Problem Statement

We have a directed graph with N vertices and M edges. The vertices are numbered from 1 through N, and the i-th edge goes from vertex U_i to vertex V_i.

You are currently at vertex 1. Determine if you can make the following move 10^{10^{100}} times to end up at vertex 1:

• choose an edge going from the vertex you are currently at, and move to the vertex that the edge points at.

Given T test cases, solve each of them.

Constraints

• All input values are integers.
• 1\leq T \leq 2\times 10^5
• 2\leq N \leq 2\times 10^5
• 1\leq M \leq 2\times 10^5
• The sum of N over all test cases is at most 2 \times 10^5.
• The sum of M over all test cases is at most 2 \times 10^5.
• 1 \leq U_i, V_i \leq N
• U_i \neq V_i
• If i\neq j, then (U_i,V_i) \neq (U_j,V_j).

Sample Input 1

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

Sample Output 1

Yes
No
No
Yes

For the 1-st test case,

• You inevitably repeat visiting vertices 1 \rightarrow 2 \rightarrow 1 \rightarrow \dots. Thus, you will end up at vertex 1 after making the move 10^{10^{100}} times, so the answer is Yes.

For the 2-nd test case,

• You inevitably repeat visiting vertices 1 \rightarrow 2 \rightarrow 3 \rightarrow 1 \rightarrow \dots. Thus, you will end up at vertex 2 after making the move 10^{10^{100}} times, so the answer is No.

Problem Statement

There are N weights numbered 1,2, \dots,N.
Using a balance, we will compare weights M times.

• Before the comparisons, prepare an empty string S.
• For the i-th comparison, put just weight A_i to the left bowl, and just weight B_i to the right.
• Then, one of the following three results is obtained.
  • If weight A_i is heavier than weight B_i,
    • append > to the tail of S.
  • If weight A_i and weight B_i have the same mass,
    • append = to the tail of S.
  • If weight A_i is lighter than weight B_i,
    • append < to the tail of S.
• The result is always accurate.

After the experiment, you will obtain a string S of length M.
Among the 3^M strings of length M consisting of >, =, and <, how many can be obtained as S by the experiment?
Since the answer can be enormous, print the answer modulo 998244353.

Constraints

• All input values are integers.
• 2 \le N \le 17
• 1 \le M \le \frac{N \times (N-1)}{2}
• 1 \le A_i < B_i \le N
• i \neq j \Rightarrow (A_i,B_i) \neq (A_j,B_j)

Sample Input 1

3 3
1 2
1 3
2 3

Sample Output 1

13

Let w be the sequence of the mass of the weights, in ascending order of weight numbers.

• If w=(5,5,5), you obtain S= ===.
• If w=(2,2,3), you obtain S= =<<.
• If w=(6,8,6), you obtain S= <=>.
• If w=(9,4,4), you obtain S= >>=.
• If w=(7,7,3), you obtain S= =>>.
• If w=(8,1,8), you obtain S= >=<.
• If w=(5,8,8), you obtain S= <<=.
• If w=(1,2,3), you obtain S= <<<.
• If w=(4,9,5), you obtain S= <<>.
• If w=(5,1,8), you obtain S= ><<.
• If w=(6,9,2), you obtain S= <>>.
• If w=(7,1,3), you obtain S= >><.
• If w=(9,7,5), you obtain S= >>>.

While there is an infinite number of possible sequences of the mass of the weights, S is always one of the 13 above.

Sample Input 2

4 4
1 4
2 3
1 3
3 4

Sample Output 2

39

Sample Input 3

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

Sample Output 3

1613763