Problem Statement

Takahashi is playing a game called Chess960. He has decided to write a code that determines if a random initial state satisfies the conditions of Chess960.

You are given a string S of length eight. S has exactly one K and Q, and exactly two R's, B's , and N's. Determine if S satisfies all of the following conditions.

• Suppose that the x-th and y-th (x < y) characters from the left of S are B; then, x and y have different parities.

• K is between two R's. More formally, suppose that the x-th and y-th (x < y) characters from the left of S are R and the z-th is K; then x< z < y.

Constraints

• S is a string of length 8 that contains exactly one K and Q, and exactly two R's, B's , and N's.

Sample Input 1

RNBQKBNR

Sample Output 1

Yes

The 3-rd and 6-th characters are B, and 3 and 6 have different parities. Also, K is between the two R's. Thus, the conditions are fulfilled.

Sample Input 2

KRRBBNNQ

Sample Output 2

No

K is not between the two R's.

Sample Input 3

BRKRBQNN

Sample Output 3

No

Problem Statement

Keyence has N bases worldwide, numbered 1 to N. Base i has W_i employees, and at 0 o'clock in Coordinated Universal Time (UTC), it is X_i o'clock at base i.

You want to hold a one-hour meeting across the entire company. Each employee can only participate in the meeting if the meeting time is completely within the 9:00-18:00 time slot at their base. Find the maximum number of employees who can participate when deciding the meeting time to allow as many employees as possible to participate.

Constraints

• 1\leq N \leq 1000
• 1\leq W_i \leq 10^6
• 0\leq X_i < 24
• All input values are integers.

Sample Input 1

3
5 0
3 3
2 18

Sample Output 1

8

Consider holding the meeting from 14:00 to 15:00 in UTC.

• The meeting is held from 14:00 to 15:00 at base 1, so the 5 employees at base 1 can participate in the meeting.
• The meeting is held from 17:00 to 18:00 at base 2, so the 3 employees at base 2 can participate in the meeting.
• The meeting is held from 8:00 to 9:00 at base 3, so the 2 employees at base 3 cannot participate in the meeting.

Thus, a total of 5+3=8 employees can participate in the meeting. No meeting time allows more employees to participate.

Sample Input 2

2
1 10
1000000 20

Sample Output 2

1000000

Sample Input 3

6
31 3
20 8
11 5
4 3
47 14
1 18

Sample Output 3

67

Problem Statement

You are given strictly increasing sequences of length N and M: A=(A _ 1,A _ 2,\ldots,A _ N) and B=(B _ 1,B _ 2,\ldots,B _ M). Here, A _ i\neq B _ j for every i and j (1\leq i\leq N,1\leq j\leq M).

Let C=(C _ 1,C _ 2,\ldots,C _ {N+M}) be a strictly increasing sequence of length N+M that results from the following procedure.

• Let C be the concatenation of A and B. Formally, let C _ i=A _ i for i=1,2,\ldots,N, and C _ i=B _ {i-N} for i=N+1,N+2,\ldots,N+M.
• Sort C in ascending order.

For each of A _ 1,A _ 2,\ldots,A _ N, B _ 1,B _ 2,\ldots,B _ M, find its position in C. More formally, for each i=1,2,\ldots,N, find k such that C _ k=A _ i, and for each j=1,2,\ldots,M, find k such that C _ k=B _ j.

Constraints

• 1\leq N,M\leq 10^5
• 1\leq A _ 1\lt A _ 2\lt\cdots\lt A _ N\leq 10^9
• 1\leq B _ 1\lt B _ 2\lt\cdots\lt B _ M\leq 10^9
• A _ i\neq B _ j for every i and j (1\leq i\leq N,1\leq j\leq M).
• All values in the input are integers.

Sample Input 1

4 3
3 14 15 92
6 53 58

Sample Output 1

1 3 4 7
2 5 6

C will be (3,6,14,15,53,58,92). Here, the 1-st, 3-rd, 4-th, 7-th elements are from A=(3,14,15,92), and the 2-nd, 5-th, 6-th elements are from B=(6,53,58).

Sample Input 2

4 4
1 2 3 4
100 200 300 400

Sample Output 2

1 2 3 4
5 6 7 8

Sample Input 3

8 12
3 4 10 15 17 18 22 30
5 7 11 13 14 16 19 21 23 24 27 28

Sample Output 3

1 2 5 9 11 12 15 20
3 4 6 7 8 10 13 14 16 17 18 19

Problem Statement

There is an integer sequence A of length N, initially A_i = i. Process a total of Q queries of the following types:

• Type 1: Change A_p to x.
• Type 2: Output A_p.
• Type 3: Repeat the operation "move the first element of A to the end" k times.
  • Formally, replace A with (A_2,A_3,\dots,A_N,A_1) k times.

Constraints

• All input values are integers.
• 1 \le N \le 10^6
• 1 \le Q \le 3 \times 10^5
• All queries satisfy the following constraints:
  • 1 \le p \le N
  • 1 \le x \le 10^6
  • 1 \le k \le 10^9

Sample Input 1

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

Sample Output 1

3
1
1000000

This input contains 5 queries.

• Initially, A=(1,2,3,4,5).
• The 1st query is Type 2: output A_3=3.
• The 2nd query is Type 1: replace A_2 with 1000000.
  • After the query, A=(1,1000000,3,4,5).
• The 3rd query is Type 3: repeat the operation "move the first element of A to the end" 4 times.
  • After the query, A=(5,1,1000000,3,4).
• The 4th query is Type 2: output A_2=1.
• The 5th query is Type 2: output A_3=1000000.

Sample Input 2

1000000 2
1 1000000 999999
3 1000000000

Sample Output 2

The output may be empty.

Problem Statement

There is a simple undirected graph G with N vertices and M edges. The vertices are numbered 1, 2, \ldots, N, and the i-th edge is an undirected edge connecting vertices A_i and B_i.

You can repeat the following two operations in any order and any number of times:

• Add one undirected edge to G
• Remove one undirected edge from G

Find the minimum number of operations to make G a simple undirected graph where all vertices have degree 2.

Constraints

• 3 \leq N \leq 8
• 0 \leq M \leq \frac{N(N-1)}{2}
• The graph G given in the input is a simple undirected graph.
• All input values are integers.

Sample Input 1

5 4
1 2
1 5
2 4
4 5

Sample Output 1

3

For example, the following three operations make G a simple undirected graph where all vertices have degree 2.

• Add an edge connecting vertices 2 and 3.
• Remove the edge connecting vertices 2 and 4.
• Add an edge connecting vertices 3 and 4.

Sample Input 2

3 0

Sample Output 2

3

Sample Input 3

6 8
1 4
1 5
2 3
2 6
3 4
3 6
4 5
4 6

Sample Output 3

2

Sample Input 4

8 21
1 4
5 7
8 4
3 4
2 5
8 1
5 1
2 8
2 1
2 4
3 1
6 7
5 8
2 7
6 8
5 4
3 8
7 3
7 8
5 3
7 4

Sample Output 4

13