Problem Statement

Takahashi is the security administrator of a certain system. In this system, a password is set as an integer sequence of length M whose elements are integers between 0 and 10^9, inclusive.

One day, N users each submitted a piece of paper on which they had written down the password. However, on every memo, exactly one value has become unreadable due to ink smudging, and that position is represented by -1. All other positions are recorded correctly.

Let S_{i,1}, S_{i,2}, \ldots, S_{i,M} denote the integer sequence written on the i-th user's memo.

Takahashi wants to check whether it is possible that all memos recorded the same password. That is, determine whether it is possible to replace the -1 in each memo with an appropriate integer between 0 and 10^9, inclusive, so that all memos become completely identical.

More precisely, determine whether there exists an integer sequence P = (P_1, P_2, \ldots, P_M) of length M, consisting of integers between 0 and 10^9 inclusive, that satisfies all of the following conditions:

• For each memo i (1 \leq i \leq N), for every position j (1 \leq j \leq M) where S_{i,j} \neq -1, it holds that S_{i,j} = P_j.

(For positions where S_{i,j} = -1, there are no constraints on the value of P_j.)

If such a P exists, print Yes; otherwise, print No.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq M \leq 2 \times 10^5
• N \times M \leq 2 \times 10^5
• Each memo contains exactly one -1.
• S_{i,j} = -1 or 0 \leq S_{i,j} \leq 10^9 (1 \leq i \leq N, 1 \leq j \leq M)
• All input values are integers.

Sample Input 1

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

Sample Output 1

Yes

Sample Input 2

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

Sample Output 2

No

Sample Input 3

5 6
-1 20 30 40 50 60
10 -1 30 40 50 60
10 20 -1 40 50 60
10 20 30 -1 50 60
10 20 30 40 -1 60

Sample Output 3

Yes

Sample Input 4

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

Sample Output 4

Yes

Sample Input 5

1 1
-1

Sample Output 5

Yes

Problem Statement

Takahashi is putting away the laundry. There are N socks in the laundry basket, and the i-th sock (1 \leq i \leq N) has an integer value A_i representing its color intensity. Different socks may have the same color intensity.

Takahashi wants to make pairs from these socks. Being a meticulous person, he requires that the absolute difference in color intensity between two socks in a pair is at most K. That is, the i-th sock and the j-th sock (i \neq j) can be paired only if |A_i - A_j| \leq K.

Each pair consists of exactly 2 socks, and each sock can be used in at most one pair. It is fine if some socks are left unpaired.

Find the maximum number of pairs of socks that Takahashi can make.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 0 \leq K \leq 10^9
• 1 \leq A_i \leq 10^9
• All input values are integers.

Sample Input 1

6 2
1 3 5 2 8 7

Sample Output 1

3

Sample Input 2

10 3
1 5 9 13 17 2 6 10 14 18

Sample Output 2

5

Sample Input 3

15 100
50 200 350 500 120 80 210 340 510 130 75 220 360 490 140

Sample Output 3

6

Problem Statement

Takahashi has a ribbon consisting of N characters, with a string S of uppercase English letters written on it from left to right.

Takahashi can cut this ribbon at most M times at distinct positions between adjacent characters.

If he makes k cuts, the ribbon is divided into k + 1 non-empty contiguous pieces. Each character belongs to exactly one piece, and the order of the pieces preserves the order in the original string S. If no cuts are made, the entire ribbon remains as one piece.

A piece is called a winning piece if the string written on it is exactly ATCODER.

Takahashi wants to maximize the number of winning pieces.

Find the maximum number of winning pieces that can be obtained with at most M cuts.

Constraints

• 1 \leq N \leq 10^6
• 0 \leq M \leq N - 1
• S is a string of length N consisting of uppercase English letters
• N, M are integers

Sample Input 1

7 0
ATCODER

Sample Output 1

1

Sample Input 2

14 1
ATCODERATCODER

Sample Output 2

2

Sample Input 3

54 8
HELLOATCODERWORLDATCODERATCODERXYZATCODERQQQATCODEREND

Sample Output 3

4

Sample Input 4

210 29
ATCODERATCODERATCODERATCODERATCODERATCODERATCODERATCODERATCODERATCODERATCODERATCODERATCODERATCODERATCODERATCODERATCODERATCODERATCODERATCODERATCODERATCODERATCODERATCODERATCODERATCODERATCODERATCODERATCODERATCODER

Sample Output 4

30

Sample Input 5

1 0
A

Sample Output 5

0

Problem Statement

Takahashi is in charge of the queue management system for a hospital's reception counter. The counter has a single queue, and patients line up at the end in order of arrival.

However, this hospital has priority cards for emergency patients. A patient holding a priority card can cut into the queue at a specified position. Takahashi needs to correctly keep track of the entire state of the queue every time a cut-in occurs.

Initially, the queue is empty. The following Q operations are given in order.

• Operation 1: 1 x — Patient with patient number x lines up at the end of the queue.
• Operation 2: 2 x k — A patient with patient number x holding a priority card is inserted at the k-th position from the front of the queue. That is, immediately after this operation, the k-th person from the front of the queue is the patient with patient number x. Patients who were at position k or later from the front before the insertion are each shifted one position back.
• Operation 3: 3 — The patient at the front of the queue is served at the counter and removed from the queue.

Note that the same patient number may appear in different operations, but they are treated as separate patients and are each independently added to the queue.

Each time operation 3 is performed, output the patient number of the removed patient.

Constraints

• 1 \leq Q \leq 2 \times 10^5
• The patient number x in operations 1 and 2 is an integer satisfying 1 \leq x \leq 10^9.
• The insertion position k in operation 2 is an integer satisfying 1 \leq k \leq (\text{length of the queue immediately before that operation}) + 1. In particular, if k equals the length of the queue immediately before the operation plus 1, the patient is added to the end.
• When operation 3 is performed, it is guaranteed that the queue is not empty.
• All values given in the input are integers.

Sample Input 1

7
1 10
1 20
2 30 2
3
2 40 1
3
3

Sample Output 1

10
40
30

Sample Input 2

6
2 5 1
1 5
2 7 3
3
3
3

Sample Output 2

5
5
7

Sample Input 3

18
1 100
1 200
2 300 1
1 400
2 500 3
3
2 600 5
3
1 700
2 800 2
3
3
2 900 1
1 1000
2 1100 4
3
3
3

Sample Output 3

300
100
500
800
900
200
400

Sample Input 4

40
1 1000000000
1 1
1 2
2 999999999 1
2 123456789 3
3
1 3
2 4 6
2 5 2
3
3
1 6
2 7 1
2 8 4
1 9
3
2 10 9
1 11
2 12 5
3
3
2 13 1
2 14 10
1 15
3
1 16
2 17 7
2 18 14
3
3
3
2 19 1
1 20
2 21 13
3
1 22
2 23 15
3
3
3

Sample Output 4

999999999
1000000000
5
7
123456789
1
13
8
2
12
19
3
4
6

Sample Input 5

2
2 1000000000 1
3

Sample Output 5

1000000000

Problem Statement

There are N cards arranged in a row from left to right. The i-th card from the left has a lowercase English letter S_i printed on it and is painted with a color P_i. Here, A, B, and C represent 3 distinct colors, and P_i is one of them. The letters and colors printed on the cards cannot be changed.

First, Takahashi writes an integer between 1 and M, inclusive, on each of the N cards. He may write the same integer on different cards.

After writing the integers, Takahashi can repeat the following operation any number of times (possibly zero) and end the process at any time:

• Choose 1 pair of adjacent cards from the currently remaining cards that have the same color and the same written integer, and remove those 2 cards. The printed letters do not need to match. After removing them, close the gaps and rearrange the remaining cards into a single row (their relative order is preserved).

You are given a string T of length L consisting of lowercase English letters, and a sequence of integers Q of length L.

Determine whether it is possible to choose how to write the integers and the sequence of operations such that, when the operations end, exactly L cards remain, and when viewed from left to right, the sequence of printed letters matches T and the sequence of written integers matches Q.

Constraints

• 1 \leq L \leq N \leq 1000
• 1 \leq M \leq N
• S is a string of length N consisting of lowercase English letters.
• P is a string of length N where each character is A, B, or C.
• T is a string of length L consisting of lowercase English letters.
• 1 \leq Q_i \leq M (1 \leq i \leq L)
• All inputs are integers or strings.

Sample Input 1

4 3 2
abcd
AABC
cd
2 3

Sample Output 1

Yes

Sample Input 2

4 2 1
abca
AABB
a
1

Sample Output 2

No

Sample Input 3

12 3 4
abcdefghijkl
AACBBACCBAAC
cfil
1 2 1 3

Sample Output 3

Yes

Sample Input 4

30 30 10
abcdefghijklmnopqrstuvwxyzabcd
AABBCCAABBCCAABBCCAAABCABCABCA
uvwxyzabcd
30 1 30 2 29 3 28 4 27 5

Sample Output 4

Yes

Sample Input 5

1 1 1
z
C
z
1

Sample Output 5

Yes