Problem Statement

Takahashi wants to print a document with N pages double-sided, where two pages of data can be printed on one sheet of paper.

At least how many sheets of paper does he need?

Constraints

• N is an integer.
• 1 \leq N \leq 100

Sample Input 1

5

Sample Output 1

3

By printing the 1-st, 2-nd pages on the 1-st sheet, 3-rd and 4-th pages on the 2-nd sheet, and 5-th page on the 3-rd sheet, we can print all the data on 3 sheets of paper.

Sample Input 2

2

Sample Output 2

1

Sample Input 3

100

Sample Output 3

50

Problem Statement

We have a bingo card with a 3\times3 grid. The square at the i-th row from the top and the j-th column from the left contains the number A_{i, j}.

The MC will choose N numbers, b_1, b_2, \cdots, b_N. If our bingo sheet contains some of those numbers, we will mark them on our sheet.

Determine whether we will have a bingo when the N numbers are chosen, that is, the sheet will contain three marked numbers in a row, column, or diagonal.

Constraints

• All values in input are integers.
• 1 \leq A_{i, j} \leq 100
• A_{i_1, j_1} \neq A_{i_2, j_2} ((i_1, j_1) \neq (i_2, j_2))
• 1 \leq N \leq 10
• 1 \leq b_i \leq 100
• b_i \neq b_j (i \neq j)

Sample Input 1

84 97 66
79 89 11
61 59 7
7
89
7
87
79
24
84
30

Sample Output 1

Yes

We will mark A_{1, 1}, A_{2, 1}, A_{2, 2}, A_{3, 3}, and complete the diagonal from the top-left to the bottom-right.

Sample Input 2

41 7 46
26 89 2
78 92 8
5
6
45
16
57
17

Sample Output 2

No

We will mark nothing.

Sample Input 3

60 88 34
92 41 43
65 73 48
10
60
43
88
11
48
73
65
41
92
34

Sample Output 3

Yes

We will mark all the squares.

Problem Statement

If there is an integer not less than 0 satisfying the following conditions, print the smallest such integer; otherwise, print -1.

• The integer has exactly N digits in base ten. (We assume 0 to be a 1-digit integer. For other integers, leading zeros are not allowed.)
• The s_i-th digit from the left is c_i. \left(i = 1, 2, \cdots, M\right)

Constraints

• All values in input are integers.
• 1 \leq N \leq 3
• 0 \leq M \leq 5
• 1 \leq s_i \leq N
• 0 \leq c_i \leq 9

Sample Input 1

3 3
1 7
3 2
1 7

Sample Output 1

702

702 satisfies the conditions - its 1-st and 3-rd digits are 7 and 2, respectively - while no non-negative integer less than 702 satisfies them.

Sample Input 2

3 2
2 1
2 3

Sample Output 2

-1

Sample Input 3

3 1
1 0

Sample Output 3

-1

Problem Statement

An SNS has N users - User 1, User 2, \cdots, User N.

Between these N users, there are some relationships - M friendships and K blockships.

For each i = 1, 2, \cdots, M, there is a bidirectional friendship between User A_i and User B_i.

For each i = 1, 2, \cdots, K, there is a bidirectional blockship between User C_i and User D_i.

We define User a to be a friend candidate for User b when all of the following four conditions are satisfied:

• a \neq b.
• There is not a friendship between User a and User b.
• There is not a blockship between User a and User b.
• There exists a sequence c_0, c_1, c_2, \cdots, c_L consisting of integers between 1 and N (inclusive) such that c_0 = a, c_L = b, and there is a friendship between User c_i and c_{i+1} for each i = 0, 1, \cdots, L - 1.

For each user i = 1, 2, ... N, how many friend candidates does it have?

Constraints

• All values in input are integers.
• 2 ≤ N ≤ 10^5
• 0 \leq M \leq 10^5
• 0 \leq K \leq 10^5
• 1 \leq A_i, B_i \leq N
• A_i \neq B_i
• 1 \leq C_i, D_i \leq N
• C_i \neq D_i
• (A_i, B_i) \neq (A_j, B_j) (i \neq j)
• (A_i, B_i) \neq (B_j, A_j)
• (C_i, D_i) \neq (C_j, D_j) (i \neq j)
• (C_i, D_i) \neq (D_j, C_j)
• (A_i, B_i) \neq (C_j, D_j)
• (A_i, B_i) \neq (D_j, C_j)

Sample Input 1

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

Sample Output 1

0 1 0 1

There is a friendship between User 2 and 3, and between 3 and 4. Also, there is no friendship or blockship between User 2 and 4. Thus, User 4 is a friend candidate for User 2.

However, neither User 1 or 3 is a friend candidate for User 2, so User 2 has one friend candidate.

Sample Input 2

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

Sample Output 2

0 0 0 0 0

Everyone is a friend of everyone else and has no friend candidate.

Sample Input 3

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

Sample Output 3

1 3 5 4 3 3 3 3 1 0

Problem Statement

You are given a string S of length N consisting of lowercase English letters.

Process Q queries of the following two types:

• Type 1: change the i_q-th character of S to c_q. (Do nothing if the i_q-th character is already c_q.)
• Type 2: answer the number of different characters occurring in the substring of S between the l_q-th and r_q-th characters (inclusive).

Constraints

• N, Q, i_q, l_q, and r_q are integers.
• S is a string consisting of lowercase English letters.
• c_q is a lowercase English letter.
• 1 \leq N \leq 500000
• 1 \leq Q \leq 20000
• |S| = N
• 1 \leq i_q \leq N
• 1 \leq l_q \leq r_q \leq N
• There is at least one query of type 2 in each testcase.

Sample Input 1

7
abcdbbd
6
2 3 6
1 5 z
2 1 1
1 4 a
1 7 d
2 1 7

Sample Output 1

3
1
5

In the first query, cdbb contains three kinds of letters: b , c , and d, so we print 3.

In the second query, S is modified to abcdzbd.

In the third query, a contains one kind of letter: a, so we print 1.

In the fourth query, S is modified to abcazbd.

In the fifth query, S does not change and is still abcazbd.

In the sixth query, abcazbd contains five kinds of letters: a, b, c, d, and z, so we print 5.

Problem Statement

Takahashi wants to grill N pieces of meat on a grilling net, which can be seen as a two-dimensional plane. The coordinates of the i-th piece of meat are \left(x_i, y_i\right), and its hardness is c_i.

Takahashi can use one heat source to grill the meat. If he puts the heat source at coordinates \left(X, Y\right), where X and Y are real numbers, the i-th piece of meat will be ready to eat in c_i \times \sqrt{\left(X - x_i\right)^2 + \left(Y-y_i\right)^2} seconds.

Takahashi wants to eat K pieces of meat. Find the time required to have K or more pieces of meat ready if he put the heat source to minimize this time.

Constraints

• All values in input are integers.
• 1 \leq N \leq 60
• 1 \leq K \leq N
• -1000 \leq x_i , y_i \leq 1000
• \left(x_i, y_i\right) \neq \left(x_j, y_j\right) \left(i \neq j \right)
• 1 \leq c_i \leq 100

Sample Input 1

4 3
-1 0 3
0 0 3
1 0 2
1 1 40

Sample Output 1

2.4

If we put the heat source at \left(-0.2, 0\right), the 1-st, 2-nd, and 3-rd pieces of meat will be ready to eat within 2.4 seconds. This is the optimal place to put the heat source.

Sample Input 2

10 5
-879 981 26
890 -406 81
512 859 97
362 -955 25
128 553 17
-885 763 2
449 310 57
-656 -204 11
-270 76 40
184 170 16

Sample Output 2

7411.2252