Problem Statement

Two characters x and y are called similar characters if and only if one of the following conditions is satisfied:

• x and y are the same character.
• One of x and y is 1 and the other is l.
• One of x and y is 0 and the other is o.

Two strings S and T, each of length N, are called similar strings if and only if:

• for all i\ (1\leq i\leq N), the i-th character of S and the i-th character of T are similar characters.

Given two length-N strings S and T consisting of lowercase English letters and digits, determine if S and T are similar strings.

Constraints

• N is an integer between 1 and 100.
• Each of S and T is a string of length N consisting of lowercase English letters and digits.

Sample Input 1

3
l0w
1ow

Sample Output 1

Yes

The 1-st character of S is l, and the 1-st character of T is 1. These are similar characters.

The 2-nd character of S is 0, and the 2-nd character of T is o. These are similar characters.

The 3-rd character of S is w, and the 3-rd character of T is w. These are similar characters.

Thus, S and T are similar strings.

Sample Input 2

3
abc
arc

Sample Output 2

No

The 2-nd character of S is b, and the 2-nd character of T is r. These are not similar characters.

Thus, S and T are not similar strings.

Sample Input 3

4
nok0
n0ko

Sample Output 3

Yes

Problem Statement

You are given a non-empty string S consisting of uppercase and lowercase English letters. Determine whether the following condition is satisfied:

• The first character of S is uppercase, and all other characters are lowercase.

Constraints

• 1 \leq |S| \leq 100 (|S| is the length of the string S.)
• Each character of S is an uppercase or lowercase English letter.

Sample Input 1

Capitalized

Sample Output 1

Yes

The first character C of Capitalized is uppercase, and all other characters apitalized are lowercase, so you should print Yes.

Sample Input 2

AtCoder

Sample Output 2

No

AtCoder contains an uppercase letter C that is not at the beginning, so you should print No.

Sample Input 3

yes

Sample Output 3

No

The first character y of yes is not uppercase, so you should print No.

Sample Input 4

A

Sample Output 4

Yes

Problem Statement

N players numbered 1 to N will play a soccer game.
When a player commits an offense, that player will receive a yellow card or a red card.
A player who satisfies one of the following conditions will be removed from the game.

• Accumulates two yellow cards.
• Receives a red card.

Once a player is removed, that player will no longer receive any cards.

You will watch this game. Initially, the players have not received any cards.
There will be Q events. Correctly answer the questions asked in the events.
There are three kinds of events, which are given in the format c x from the input, where c is 1, 2, or 3. The events are as follows.

• 1 x: Player x receives a yellow card.
• 2 x: Player x receives a red card.
• 3 x: You are asked whether player x has been removed from the game. Answer Yes or No.

Constraints

• 1 \leq N \leq 100
• 1 \leq Q \leq 100
• 1 \leq x \leq N in all events.
• There is at least one event of the third kind.
• A player who has been removed will no longer receive any cards.
• All values in the input are integers.

Sample Input 1

3 9
3 1
3 2
1 2
2 1
3 1
3 2
1 2
3 2
3 3

Sample Output 1

No
No
Yes
No
Yes
No

Here are all the events in chronological order.

In the 1-st event, you are asked whether player 1 has been removed from the game. Player 1 has not been removed, so you should print No.
In the 2-nd event, you are asked whether player 2 has been removed from the game. Player 2 has not been removed, so you should print No.
In the 3-rd event, player 2 receives a yellow card.
In the 4-th event, player 1 receives a red card and is removed from the game.
In the 5-th event, you are asked whether player 1 has been removed from the game. Player 1 has been removed, so you should print Yes.
In the 6-th event, you are asked whether player 2 has been removed from the game. Player 2 has not been removed, so you should print No.
In the 7-th event, player 2 receives a yellow card and is removed from the game.
In the 8-th event, you are asked whether player 2 has been removed from the game. Player 2 has been removed, so you should print Yes.
In the 9-th event, you are asked whether player 3 has been removed from the game. Player 3 has not been removed, so you should print No.

Problem Statement

There are N players numbered 1 to N, who have played a round-robin tournament. For every match in this tournament, one player won and the other lost.

The results of the matches are given as N strings S_1,S_2,\ldots,S_N of length N each, in the following format:

• If i\neq j, the j-th character of S_i is o or x. o means that player i won against player j, and x means that player i lost to player j.

• If i=j, the j-th character of S_i is -.

The player with more wins ranks higher. If two players have the same number of wins, the player with the smaller player number ranks higher. Report the player numbers of the N players in descending order of rank.

Constraints

• 2\leq N\leq 100
• N is an integer.
• S_i is a string of length N consisting of o, x, and -.
• S_1,\ldots,S_N conform to the format described in the problem statement.

Sample Input 1

3
-xx
o-x
oo-

Sample Output 1

3 2 1

Player 1 has 0 wins, player 2 has 1 win, and player 3 has 2 wins. Thus, the player numbers in descending order of rank are 3,2,1.

Sample Input 2

7
-oxoxox
x-xxxox
oo-xoox
xoo-ooo
ooxx-ox
xxxxx-x
oooxoo-

Sample Output 2

4 7 3 1 5 2 6

Both players 4 and 7 have 5 wins, but player 4 ranks higher because their player number is smaller.

Problem Statement

You are given positive integers N and Q, and a string S of length N consisting of lowercase English letters.

Process Q queries. Each query is of one of the following two types.

• 1 x: Perform the following x times in a row: delete the last character of S and append it to the beginning.
• 2 x: Print the x-th character of S.

Constraints

• 2 \le N \le 5 \times 10^5
• 1 \le Q \le 5 \times 10^5
• 1 \le x \le N
• |S|=N
• S consists of lowercase English letters.
• At least one query in the format 2 x.
• N, Q, x are all integers.

Sample Input 1

3 3
abc
2 2
1 1
2 2

Sample Output 1

b
a

In the 1-st query, S is abc, so the 2-nd character b should be printed. In the 2-nd query, S is changed from abc to cab. In the 3-rd query, S is cab, so the 2-nd character a should be printed.

Sample Input 2

10 8
dsuccxulnl
2 4
2 7
1 2
2 7
1 1
1 2
1 3
2 5

Sample Output 2

c
u
c
u

Problem Statement

We have an empty box.
Takahashi can cast the following two spells any number of times in any order.

• Spell A: puts one new ball into the box.
• Spell B: doubles the number of balls in the box.

Tell us a way to have exactly N balls in the box with at most \mathbf{120} casts of spells.
It can be proved that there always exists such a way under the Constraints given.

There is no way other than spells to alter the number of balls in the box.

Constraints

• 1 \leq N \leq 10^{18}
• All values in input are integers.

Sample Input 1

5

Sample Output 1

AABA

This changes the number of balls as follows: 0 \xrightarrow{A} 1\xrightarrow{A} 2 \xrightarrow{B}4\xrightarrow{A} 5.
There are also other acceptable outputs, such as AAAAA.

Sample Input 2

14

Sample Output 2

BBABBAAAB

This changes the number of balls as follows: 0 \xrightarrow{B} 0 \xrightarrow{B} 0 \xrightarrow{A}1 \xrightarrow{B} 2 \xrightarrow{B} 4 \xrightarrow{A}5 \xrightarrow{A}6 \xrightarrow{A} 7 \xrightarrow{B}14.
It is not required to minimize the length of S.

Problem Statement

Takahashi is playing a game.

The game consists of N stages numbered 1,2,\ldots,N. Initially, only stage 1 can be played.

For each stage i ( 1\leq i \leq N-1 ) that can be played, you can perform one of the following two actions at stage i:

• Spend A_i seconds to clear stage i. This allows you to play stage i+1.
• Spend B_i seconds to clear stage i. This allows you to play stage X_i.

Ignoring the times other than the time spent to clear the stages, how many seconds will it take at the minimum to be able to play stage N?

Constraints

• 2 \leq N \leq 2\times 10^5
• 1 \leq A_i, B_i \leq 10^9
• 1 \leq X_i \leq N
• All input values are integers.

Sample Input 1

5
100 200 3
50 10 1
100 200 5
150 1 2

Sample Output 1

350

By acting as follows, you will be allowed to play stage 5 in 350 seconds.

• Spend 100 seconds to clear stage 1, which allows you to play stage 2.
• Spend 50 seconds to clear stage 2, which allows you to play stage 3.
• Spend 200 seconds to clear stage 3, which allows you to play stage 5.

Sample Input 2

10
1000 10 9
1000 10 10
1000 10 2
1000 10 3
1000 10 4
1000 10 5
1000 10 6
1000 10 7
1000 10 8

Sample Output 2

90

Sample Input 3

6
1000000000 1000000000 1
1000000000 1000000000 1
1000000000 1000000000 1
1000000000 1000000000 1
1000000000 1000000000 1

Sample Output 3

5000000000

Problem Statement

You are given a sequence A = (A_1, A_2, \dots, A_N) of length N and a positive integer K (at most N).
For each i = 1, 2, \dots, N, solve the following problem:

• When you choose K elements from A that include A_i, find the maximum possible GCD (greatest common divisor) of those chosen elements.

Constraints

• 1 \leq K \leq N \leq 1.2 \times 10^6
• 1 \leq A_i \leq 10^6
• All input values are integers.

Sample Input 1

5 2
3 4 6 7 12

Sample Output 1

3
4
6
1
6

For i=1, choosing A_1 and A_3 yields \gcd(\lbrace 3,6 \rbrace) = 3, which is the maximum.
For i=2, choosing A_2 and A_5 yields \gcd(\lbrace 4,12 \rbrace) = 4, which is the maximum.
For i=3, choosing A_3 and A_5 yields \gcd(\lbrace 6,12 \rbrace) = 6, which is the maximum.
For i=4, choosing A_4 and A_2 yields \gcd(\lbrace 7,4 \rbrace) = 1, which is the maximum.
For i=5, choosing A_5 and A_3 yields \gcd(\lbrace 12,6 \rbrace) = 6, which is the maximum.

Sample Input 2

3 3
6 10 15

Sample Output 2

1
1
1

Sample Input 3

10 3
414003 854320 485570 52740 833292 625990 909680 885153 435420 221663

Sample Output 3

59
590
590
879
879
590
20
879
590
59

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