Problem Statement

Given integers R, C, and a 2 \times 2 matrix A, print A_{R,C}.

Constraints

• All values in input are integers.
• 1 \le R,C \le 2
• 0 \le A_{i,j} \le 100

Sample Input 1

1 2
1 0
0 1

Sample Output 1

0

We have A_{1,2}=0.

Sample Input 2

2 2
1 2
3 4

Sample Output 2

4

We have A_{2,2}=4.

Sample Input 3

2 1
90 80
70 60

Sample Output 3

70

We have A_{2,1}=70.

Problem Statement

You are given an integer X between 1 and 3, inclusive.

Output an integer between 1 and 3, inclusive, that is different from X.

Constraints

• X is an integer between 1 and 3, inclusive.

Sample Input 1

1

Sample Output 1

2

The integers between 1 and 3, inclusive, that are different from X(=1) are 2 and 3.

Thus, outputing either 2 or 3 will be accepted.

Sample Input 2

2

Sample Output 2

3

Sample Input 3

3

Sample Output 3

2

Problem Statement

N students took an exam. The students are labeled as Student 1, Student 2, \dots, Student N, and Student i scored a_i points.

A student who scored less than P points are considered to have failed the exam and cannot earn the credit. Find the number of students who failed the exam.

Constraints

• 1 \leq N \leq 10^5
• 1 \leq P \leq 100
• 0 \leq a_i \leq 100 (1 \leq i \leq N)
• All values in input are integers.

Sample Input 1

4 50
80 60 40 0

Sample Output 1

2

Students 1 and 2, who scored 80 and 60 points, respectively, succeeded in scoring at least 50 points to earn the credit.
On the other hand, Students 3 and 4, who scored 40 and 0 points, respectively, fell below 50 points and failed the exam. Thus, the answer is 2.

Sample Input 2

3 90
89 89 89

Sample Output 2

3

Sample Input 3

2 22
6 37

Sample Output 3

1

Problem Statement

You are given an odd number N that is at least 3.

There is a grid with N rows and N columns, where all cells are initially empty. Now, you will write integers in each cell of this grid according to the following procedure. Let (i,j) denote the cell at the (i+1)-th row from the top and (j+1)-th column from the left (0\leq i<N, 0\leq j<N).

1. Write 1 in cell (0,\frac{N-1}{2}).
2. Repeat the following operation N^2-1 times:
   • Let (r,c) be the cell where an integer was written last time, and k be the integer written. If cell ((r-1) \bmod N, (c+1) \bmod N) is empty, write k+1 in that cell; otherwise, write k+1 in cell ((r+1) \bmod N,c). Here, x \bmod N denotes the remainder when x is divided by N.

Find the integer that will be written in each cell in this procedure. It can be proved that each cell will have an integer written in it exactly once.

Constraints

• 3\leq N \leq 99
• N is an odd number.

Sample Input 1

3

Sample Output 1

8 1 6
3 5 7
4 9 2

Integers are written in each cell as follows:

1. Write 1 in cell (0,\frac{3-1}{2})=(0,1).
2. Cell ((0-1) \bmod 3, (1+1) \bmod 3)=(2,2) is empty, so write 2 there.
3. Cell ((2-1) \bmod 3, (2+1) \bmod 3)=(1,0) is empty, so write 3 there.
4. Cell ((1-1) \bmod 3, (0+1) \bmod 3)=(0,1) is not empty, so write 4 in cell ((1+1) \bmod 3,0)=(2,0).
5. \vdots

Sample Input 2

5

Sample Output 2

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

Problem Statement

Consider a two-dimensional coordinate plane, where the x-axis is oriented to the right, and the y-axis is oriented upward.

In this plane, there is a quadrilateral without self-intersection.
The coordinates of the four vertices are (A_x,A_y), (B_x,B_y), (C_x,C_y), and (D_x,D_y), in counter-clockwise order.

Determine whether this quadrilateral is convex.

Here, a quadrilateral is convex if and only if all four interior angles are less than 180 degrees.

Constraints

• -100 \leq A_x,A_y,B_x,B_y,C_x,C_y,D_x,D_y \leq 100
• All values in input are integers.
• The given four points are the four vertices of a quadrilateral in counter-clockwise order.
• The quadrilateral formed by the given four points has no self-intersection and is non-degenerate. That is,
  • no two vertices are at the same coordinates;
  • no three vertices are colinear; and
  • no two edges that are not adjacent have a common point.

Sample Input 1

0 0
1 0
1 1
0 1

Sample Output 1

Yes

The given quadrilateral is a square, whose four interior angles are all 90 degrees. Thus, this quadrilateral is convex.

Sample Input 2

0 0
1 1
-1 0
1 -1

Sample Output 2

No

The angle A is 270 degrees. Thus, this quadrilateral is not convex.

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

You are given integers N and M.

Print all integer sequences (A_1, A_2, \ldots, A_N) of length N that satisfy all of the following conditions, in lexicographical order.

• 1 \leq A_i
• A_{i - 1} + 10 \leq A_i for each integer i from 2 through N
• A_N \leq M

Constraints

• 2 \leq N \leq 12
• 10N - 9 \leq M \leq 10N
• All input values are integers.

Sample Input 1

3 23

Sample Output 1

10
1 11 21
1 11 22
1 11 23
1 12 22
1 12 23
1 13 23
2 12 22
2 12 23
2 13 23
3 13 23

(1, 11, 21), (1, 11, 22), (1, 11, 23), (1, 12, 22), (1, 12, 23), (1, 13, 23), (2, 12, 22), (2, 12, 23), (2, 13, 23), (3, 13, 23) are the 10 sequences that satisfy the conditions.

Problem Statement

You are given a string S of length N consisting of 0 and 1. It describes a length-N sequence A=(A _ 1,A _ 2,\ldots,A _ N). If the i-th character of S (1\leq i\leq N) is 0, then A _ i=0; if it is 1, then A _ i=1.

Find the following:

\[\sum _ {1\leq i\leq j\leq N}(\cdots((A _ i\barwedge A _ {i+1})\barwedge A _ {i+2})\barwedge\cdots\barwedge A _ j)\]

More formally, find \displaystyle\sum _ {i=1} ^ {N}\sum _ {j=i} ^ Nf(i,j) for f(i,j)\ (1\leq i\leq j\leq N) defined as follows:

\[f(i,j)=\left\{\begin{matrix} A _ i&(i=j)\\ f(i,j-1)\barwedge A _ j\quad&(i\lt j) \end{matrix}\right.\]

Here, \barwedge, NAND, is a binary operator satisfying the following:

\[0\barwedge0=1,0\barwedge1=1,1\barwedge0=1,1\barwedge1=0.\]

Constraints

• 1\leq N\leq10^6
• S is a string of length N consisting of 0 and 1.
• All input values are integers.

Sample Input 1

5
00110

Sample Output 1

9

Here are the values of f(i,j) for the pairs (i,j) such that 1\leq i\leq j\leq N:

• f(1,1)=0=0
• f(1,2)=0\barwedge0=1
• f(1,3)=(0\barwedge0)\barwedge1=0
• f(1,4)=((0\barwedge0)\barwedge1)\barwedge1=1
• f(1,5)=(((0\barwedge0)\barwedge1)\barwedge1)\barwedge0=1
• f(2,2)=0=0
• f(2,3)=0\barwedge1=1
• f(2,4)=(0\barwedge1)\barwedge1=0
• f(2,5)=((0\barwedge1)\barwedge1)\barwedge0=1
• f(3,3)=1=1
• f(3,4)=1\barwedge1=0
• f(3,5)=(1\barwedge1)\barwedge0=1
• f(4,4)=1=1
• f(4,5)=1\barwedge0=1
• f(5,5)=0=0

Their sum is 0+1+0+1+1+0+1+0+1+1+0+1+1+1+0=9, so print 9.

Note that \barwedge does not satisfy the associative property. For instance, (1\barwedge1)\barwedge0=0\barwedge0=1\neq0=1\barwedge1=1\barwedge(1\barwedge0).

Sample Input 2

30
101010000100101011010011000010

Sample Output 2

326

Problem Statement

There are N products for sale in a store. The i-th product has a price of P_i yen, a utility value of U_i, and a color C_i.

You will choose some subset of these N products to buy (possibly none). The total price of the chosen products must be at most X yen.

Your satisfaction is S + T \times K, where S is the sum of utilities of the chosen products, and T is the number of distinct colors among the chosen products. Here, K is a given constant.

You will choose products to maximize your satisfaction. Find the maximized satisfaction.

Constraints

• 1 \leq N \leq 500
• 1 \leq X \leq 50000
• 1 \leq K \leq 10^9
• 1 \leq P_i \leq X (1 \leq i \leq N)
• 1 \leq U_i \leq 10^9 (1 \leq i \leq N)
• 1 \leq C_i \leq N (1 \leq i \leq N)
• All input values are integers.

Sample Input 1

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

Sample Output 1

17

If you buy the 1st and 2nd products, the total utility S is 7, and the number of distinct colors T is 2. Thus, your satisfaction is 7 + 2 \times 5 = 17. No purchase plan makes your satisfaction 18 or greater, so the answer is 17.

Sample Input 2

5 30 3
5 4 3
11 20 1
9 10 4
7 5 2
16 15 4

Sample Output 2

44

If you buy the 2nd, 3rd, and 4th products, the total utility S is 35, and the number of distinct colors T is 3. Thus, your satisfaction is 35 + 3 \times 3 = 44. No purchase plan makes your satisfaction 45 or greater, so the answer is 44.

Sample Input 3

22 75 6426
9 309 9
5 470 5
17 481 12
27 352 14
1 191 18
7 353 20
9 99 15
20 401 17
46 434 19
11 459 22
10 317 19
15 440 18
17 438 19
25 461 22
5 320 22
1 476 21
11 315 3
8 112 9
11 438 13
19 362 8
10 422 13
10 152 21

Sample Output 3

67717