Problem Statement

There are 4 squares lined up horizontally.

You are given a string S of length 4 consisting of 0 and 1.
If the i-th character of S is 1, there is a person in the i-th square from the left;
if the i-th character of S is 0, there is no person in the i-th square from the left.

Now, everyone will move to the next square to the right simultaneously. By this move, the person who was originally in the rightmost square will disappear.

Determine if there will be a person in each square after the move. Print the result as a string in the same format as S. (See also Sample Input / Output for clarity.)

Constraints

• S is a string of length 4 consisting of 0 and 1.

Sample Input 1

1011

Sample Output 1

0101

After the move, the person who was originally in the 1-st square will move to the 2-nd square,
the person in the 3-rd square to the 4-th square,
and the person in the 4-th square will disappear.

Sample Input 2

0000

Sample Output 2

0000

Sample Input 3

1111

Sample Output 3

0111

Problem Statement

There are N people numbered Person 1, Person 2, \dots, and Person N. Person i has a family name s_i and a given name t_i.

Consider giving a nickname to each of the N people. Person i's nickname a_i should satisfy all the conditions below.

• a_i coincides with Person i's family name or given name. In other words, a_i = s_i and/or a_i = t_i holds.
• a_i does not coincide with the family name and the given name of any other person. In other words, for all integer j such that 1 \leq j \leq N and i \neq j, it holds that a_i \neq s_j and a_i \neq t_j.

Is it possible to give nicknames to all the N people? If it is possible, print Yes; otherwise, print No.

Constraints

• 2 \leq N \leq 100
• N is an integer.
• s_i and t_i are strings of lengths between 1 and 10 (inclusive) consisting of lowercase English alphabets.

Sample Input 1

3
tanaka taro
tanaka jiro
suzuki hanako

Sample Output 1

Yes

The following assignment satisfies the conditions of nicknames described in the Problem Statement: a_1 = taro, a_2 = jiro, a_3 = hanako. (a_3 may be suzuki, too.)
However, note that we cannot let a_1 = tanaka, which violates the second condition of nicknames, since Person 2's family name s_2 is tanaka too.

Sample Input 2

3
aaa bbb
xxx aaa
bbb yyy

Sample Output 2

No

There is no way to give nicknames satisfying the conditions in the Problem Statement.

Sample Input 3

2
tanaka taro
tanaka taro

Sample Output 3

No

There may be a pair of people with the same family name and the same given name.

Sample Input 4

3
takahashi chokudai
aoki kensho
snu ke

Sample Output 4

Yes

We can let a_1 = chokudai, a_2 = kensho, and a_3 = ke.

Problem Statement

We define sequences S_n as follows.

• S_1 is a sequence of length 1 containing a single 1.
• S_n (n is an integer greater than or equal to 2) is a sequence obtained by concatenating S_{n-1}, n, S_{n-1} in this order.

For example, S_2 and S_3 is defined as follows.

• S_2 is a concatenation of S_1, 2, and S_1, in this order, so it is 1,2,1.
• S_3 is a concatenation of S_2, 3, and S_2, in this order, so it is 1,2,1,3,1,2,1.

Given N, print the entire sequence S_N.

Constraints

• N is an integer.
• 1 \leq N \leq 16

Sample Input 1

2

Sample Output 1

1 2 1

As described in the Problem Statement, S_2 is 1,2,1.

Sample Input 2

1

Sample Output 2

1

Sample Input 3

4

Sample Output 3

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

• S_4 is a concatenation of S_3, 4, and S_3, in this order.

Problem Statement

We have a horizontal cylinder. Given Q queries, process them in the given order.
Each query is of one of the following two types.

• 1 x c: Insert c balls, with a number x written on each of them, to the right end of the cylinder.
• 2 c: Take out the c leftmost balls contained in the cylinder and print the sum of the numbers written on the balls that have been taken out.

We assume that the balls do never change their order in the cylinder.

Constraints

• 1 \leq Q \leq 2\times 10^5
• 0 \leq x \leq 10^9
• 1 \leq c \leq 10^9
• Whenever a query of type 2 c is given, there are c or more balls in the cylinder.
• All values in input are integers.

Sample Input 1

4
1 2 3
2 2
1 3 4
2 3

Sample Output 1

4
8

• For the 1-st query, insert 3 balls, with a number 2 written on each of them, to the right end of the cylinder.
  The cylinder has now balls with numbers (2,2,2) written on them, from left to right.
• For the 2-nd query, take out the 2 leftmost balls contained in the cylinder.
  The numbers written on the balls taken out are 2,2, for a sum of 4, which should be printed. The cylinder has now a ball with a number (2) written on it, from left to right.
• For the 3-rd query, insert 4 balls, with a number 3 written on each of them, to the right end of the cylinder.
  The cylinder has now balls with numbers (2,3,3,3,3) written on them, from left to right.
• For the 4-th query, take out the 3 leftmost balls contained in the cylinder.
  The numbers written on the balls taken out are 2,3,3, for a sum of 8, which should be printed. The cylinder has now balls with numbers (3,3) written on them, from left to right.

Sample Input 2

2
1 1000000000 1000000000
2 1000000000

Sample Output 2

1000000000000000000

Sample Input 3

5
1 1 1
1 1 1
1 1 1
1 1 1
1 1 1

Sample Output 3

There may be nothing you should print.

Problem Statement

We have a number sequence A = (A_1, A_2, \dots, A_N) of length N and integers X and Y. Find the number of pairs of integers (L, R) satisfying all the conditions below.

• 1 \leq L \leq R \leq N
• The maximum value of A_L, A_{L+1}, \dots, A_R is X, and the minimum is Y.

Constraints

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

Sample Input 1

4 3 1
1 2 3 1

Sample Output 1

4

4 pairs satisfy the conditions: (L,R)=(1,3),(1,4),(2,4),(3,4).

Sample Input 2

5 2 1
1 3 2 4 1

Sample Output 2

0

No pair (L,R) satisfies the condition.

Sample Input 3

5 1 1
1 1 1 1 1

Sample Output 3

15

It may hold that X=Y.

Sample Input 4

10 8 1
2 7 1 8 2 8 1 8 2 8

Sample Output 4

36

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

Problem Statement

There are N competitive programmers.
The i-th competitive programmer belongs to University A_i, is good at Subject B_i, and has a power of C_i.

Consider a team consisting of some of the N people. Let us call such a team a dream team if both of the following conditions are satisfied:

• Any two people belonging to the team belong to different universities.
• Any two people belonging to the team are good at different subjects.

Let k be the maximum possible number of members of a dream team. For each i=1,2,\ldots,k, solve the following question.

Question: find the maximum sum of power of people belonging to a dream team consisting of i people.

Constraints

• 1 \leq N \leq 3\times 10^4
• 1 \leq A_i,B_i \leq 150
• 1 \leq C_i \leq 10^9
• All values in input are integers.

Sample Input 1

3
1 1 100
1 20 10
2 1 1

Sample Output 1

2
100
11

• The sum of power of members of a dream team consisting of exactly 1 person is 100, when the team consists of the 1-st competitive programmer.
• The sum of power of members of a dream team consisting of exactly 2 people is 11, when the team consists of the 2-nd and the 3-rd competitive programmers.
• It is impossible to form a dream team consisting of exactly 3 people.

Sample Input 2

10
1 4 142135623
2 6 457513110
3 1 622776601
5 1 961524227
2 2 360679774
2 4 494897427
3 7 416573867
5 2 915026221
1 7 320508075
5 3 851648071

Sample Output 2

4
961524227
1537802822
2032700249
2353208324

Problem Statement

There are N people called Person 1, Person 2, \dots, Person N, lined up in a row in the order of (1,2,\dots,N) from the front. Person i is wearing Color c_i.
Takahashi repeated the following operation K times: choose two People i and j arbitrarily and swap the positions of Person i and Person j.
After the K operations have ended, the color that the i-th person from the front is wearing coincided with c_i, for every integer i such that 1 \leq i \leq N.
How many possible permutations of people after the K operations are there? Find the count modulo 998244353.

Constraints

• 2 \leq N \leq 200000
• 1 \leq K \leq 10^9
• 1 \leq c_i \leq N
• All values in input are integers.

Sample Input 1

4 1
1 1 2 1

Sample Output 1

3

Here is a comprehensive list of possible Takahashi's operations and permutations of people after each operation.

• Swap the positions of Person 1 and Person 2, resulting in a permutation (2, 1, 3, 4).
• Swap the positions of Person 1 and Person 4, resulting in a permutation (4, 2, 3, 1).
• Swap the positions of Person 2 and Person 4, resulting in a permutation (1, 4, 3, 2).

Sample Input 2

3 3
1 1 2

Sample Output 2

1

Here is an example of a possible sequence of Takahashi's operations.

• In the 1-st operation, he swaps the positions of Person 1 and Person 3, resulting in a permutation (3, 2, 1).
  In the 2-nd operation, he swaps the positions of Person 2 and Person 3, resulting in a permutation (2, 3, 1).
  In the 3-rd operation, he swaps the positions of Person 1 and Person 3, resulting in a permutation (2, 1, 3).

Note that, during the sequence of operations, the color that the i-th person from the front is wearing does not necessarily coincide with c_i.

Sample Input 3

10 4
2 7 1 8 2 8 1 8 2 8

Sample Output 3

132