Problem Statement

We have a grid with 2 horizontal rows and 2 vertical columns.
Each of the squares is black or white, and there are at least 2 black squares.
The colors of the squares are given to you as strings S_1 and S_2, as follows.

• If the j-th character of S_i is #, the square at the i-th row from the top and j-th column from the left is black.
• If the j-th character of S_i is ., the square at the i-th row from the top and j-th column from the left is white.

You can travel between two different black squares if and only if they share a side.
Determine whether it is possible to travel from every black square to every black square (directly or indirectly) by only passing black squares.

Constraints

• Each of S_1 and S_2 is a string with two characters consisting of # and ..
• S_1 and S_2 have two or more #s in total.

Sample Input 1

##
.#

Sample Output 1

Yes

It is possible to directly travel between the top-left and top-right black squares and between top-right and bottom-right squares.
These two moves enable us to travel from every black square to every black square, so the answer is Yes.

Sample Input 2

.#
#.

Sample Output 2

No

It is impossible to travel between the top-right and bottom-left black squares, so the answer is No.

Problem Statement

In AtCoder, the top 10 rated players' usernames are displayed with a gold crown, and the top-rated player's username is displayed with a platinum crown.

At the start of this contest, the usernames and ratings of the top 10 rated players in the algorithm category are as follows:

tourist 3858
ksun48 3679
Benq 3658
Um_nik 3648
apiad 3638
Stonefeang 3630
ecnerwala 3613
mnbvmar 3555
newbiedmy 3516
semiexp 3481

You are given the username S of one of these players. Print that player's rating.

Constraints

• S is equal to one of the usernames of the top 10 rated players in the algorithm category.

Sample Input 1

tourist

Sample Output 1

3858

At the start of this contest, the rating of tourist in the algorithm category is 3858.

Sample Input 2

semiexp

Sample Output 2

3481

At the start of this contest, the rating of semiexp in the algorithm category is 3481.

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

You are given a string S consisting of lowercase English letters. Remove all occurrences of the most frequent character(s) in S, then output the remaining characters concatenated in their original order.

If there are multiple characters with the maximum frequency, remove all of them.

Constraints

• 1 \le |S| \le 100
• S is a string consisting of lowercase English letters.

Sample Input 1

mississippi

Sample Output 1

mpp

The most frequent characters in mississippi are s and i, each appearing four times. Removing all occurrences of s and i yields the string mpp.

Sample Input 2

atcoder

Sample Output 2

Sample Input 3

beginner

Sample Output 3

bgir

Problem Statement

In the AtCoder Kingdom, there are N castle walls numbered from 1 through N. There are also M turrets.

Turret i guards castle walls numbered from L_i through R_i.

When a turret is destroyed, the castle walls that were guarded by that turret are no longer guarded by that turret.

What is the minimum number of turrets that need to be destroyed so that at least one castle wall is not guarded by any turret?

Constraints

• 1 \leq N \leq 10^6
• 1 \leq M \leq 2 \times 10^5
• 1 \leq L_i \leq R_i \leq N (1 \leq i \leq M)
• All input values are integers.

Sample Input 1

10 4
1 6
4 5
5 10
7 10

Sample Output 1

1

If turret 1 is destroyed, no turret guards castle wall 3. Also, if no turrets are destroyed, all castle walls are guarded by some turret. Therefore, output 1.

Sample Input 2

5 2
1 2
3 4

Sample Output 2

0

Since no turret guards castle wall 5, there already exists a castle wall not guarded by any turret without destroying any turrets. Therefore, output 0.

Sample Input 3

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

Sample Output 3

3

Problem Statement

Print all strictly increasing integer sequences of length N where all elements are between 1 and M (inclusive), in lexicographically ascending order.

Notes

For two integer sequences of the same length A_1,A_2,\dots,A_N and B_1,B_2,\dots,B_N, A is said to be lexicographically earlier than B if and only if:

• there is an integer i (1 \le i \le N) such that A_j=B_j for all integers j satisfying 1 \le j < i, and A_i < B_i.

An integer sequence A_1,A_2,\dots,A_N is said to be strictly increasing if and only if:

• A_i < A_{i+1} for all integers i (1 \le i \le N-1).

Constraints

• 1 \le N \le M \le 10
• All values in input are integers.

Sample Input 1

2 3

Sample Output 1

1 2 
1 3 
2 3 

The sought sequences are (1,2),(1,3),(2,3), which should be printed in lexicographically ascending order.

Sample Input 2

3 5

Sample Output 2

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

Problem Statement

You are given a string S of length N consisting of the characters ., o, and ?. Among the strings that can be obtained by replacing every ? in S independently with either . or o, let X be the set of strings that satisfy all of the following conditions:

• The number of os is exactly K.
• No two os are adjacent.

It is guaranteed that X is non‑empty.

Print a string T of length N that satisfies the following (let T_i denote the i‑th character of T):

• If the i‑th character of every string in X is ., then T_i= ..
• If the i‑th character of every string in X is o, then T_i= o.
• If X contains both a string whose i‑th character is . and a string whose i‑th character is o, then T_i= ?.

Constraints

• 1 \le N \le 2 \times 10^{5}
• 0 \le K
• S is a string of length N consisting of ., o, ?.
• X is non‑empty.
• All given numerical values are integers.

Sample Input 1

4 2
o???

Sample Output 1

o.??

The set X consists of the two strings o.o. and o..o.

• The 1st character of every string in X is o, so T_1 is o.
• The 2nd character of every string in X is ., so T_2 is ..
• The 3rd character of a string in X can be either . or o, so T_3 is ?.

Sample Input 2

5 2
?????

Sample Output 2

?????

Sample Input 3

7 3
.o???o.

Sample Output 3

.o.o.o.

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

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

You are given Q queries to process in order. The i-th query is explained below.

• You are given positive integers l_i,r_i,L_i,R_i. Print Yes if it is possible to rearrange the subsequence (A_{l_i},A_{l_i+1},\ldots,A_{r_i}) to match the subsequence (B_{L_i},B_{L_i+1},\ldots,B_{R_i}), and No otherwise.

Constraints

• 1\leq N,Q\leq 2\times 10^5
• 1\leq A_i,B_i\leq N
• 1\leq l_i \leq r_i\leq N
• 1\leq L_i \leq R_i\leq N
• All input values are integers.

Sample Input 1

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

Sample Output 1

Yes
No
No
Yes

• For the 1st query, it is possible to rearrange (1,2,3) to match (2,3,1). Hence, we print Yes.
• For the 2nd query, it is impossible to rearrange (1,2) in any way to match (1,4,2). Hence, we print No.
• For the 3rd query, it is impossible to rearrange (1,2,3,2) in any way to match (3,1,4,2). Hence, we print No.
• For the 4th query, it is possible to rearrange (1,2,3,2,4) to match (2,3,1,4,2). Hence, we print Yes.

Sample Input 2

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

Sample Output 2

Yes
Yes
No
No