Problem Statement

In the hexadecimal system, where the digits ABCDEF corresponding to 10,11,12,13,14, and 15 are used in addition to 0123456789, every integer between 0 and 255 is represented as a 1- or 2-digit numeral.
For example, 0 and 12 are represented as 1-digit hexadecimal numerals 0 and C; 99 and 255 are represented as 2-digit hexadecimals 63 and FF.

Given an integer N between 0 and 255, convert it to an exactly two-digit hexadecimal numeral, prepending leading 0s if necessary.

Notes

The judge is case-sensitive. Specifically, you cannot use abcdef as hexadecimal digits instead of ABCDEF.

Constraints

• 0 \leq N \leq 255
• N is an integer.

Sample Input 1

99

Sample Output 1

63

99 is represented as 63 in hexadecimal.

Sample Input 2

12

Sample Output 2

0C

12 is represented as C in hexadecimal.
Since we ask you to convert it to a two-digit hexadecimal numeral, the answer is 0C, where 0 is prepended to C.

Sample Input 3

0

Sample Output 3

00

Sample Input 4

255

Sample Output 4

FF

Problem Statement

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

Uppercase each character of S and print the resulting string T.

Constraints

• S is a string consisting of lowercase English letters whose length is between 1 and 100, inclusive.

Sample Input 1

abc

Sample Output 1

ABC

Uppercase each character of abc, and you have ABC.

Sample Input 2

a

Sample Output 2

A

Sample Input 3

abcdefghjiklnmoqprstvuwxyz

Sample Output 3

ABCDEFGHJIKLNMOQPRSTVUWXYZ

Problem Statement

Print the color of the cell at the R-th row from the top and C-th column from the left in the following grid with 15 vertical rows and 15 horizontal columns.

Constraints

• 1 \leq R, C \leq 15
• R and C are integers.

Sample Input 1

3 5

Sample Output 1

black

In the grid above, the cell at the 3-rd row from the top and 5-th column from the left is black. Thus, black should be printed.

Sample Input 2

4 5

Sample Output 2

white

In the grid above, the cell at the 4-th row from the top and 5-th column from the left is white. Thus, white should be printed.

Problem Statement

You are given a 4-digit PIN: X_1X_2X_3X_4, which may begin with a 0. The PIN is said to be weak when it satisfies one of the following conditions:

• All of the four digits are the same.
• For each integer i such that 1\leq i\leq 3, X_{i+1} follows X_i. Here, j+1 follows j for each 0\leq j\leq 8, and 0 follows 9.

If the given PIN is weak, print Weak; otherwise, print Strong.

Constraints

• 0 \leq X_1, X_2, X_3, X_4 \leq 9
• X_1, X_2, X_3, and X_4 are integers.

Sample Input 1

7777

Sample Output 1

Weak

All four digits are 7, satisfying the first condition, so this PIN is weak.

Sample Input 2

0112

Sample Output 2

Strong

The first and second digits differ, and the third digit does not follow the second digit, so neither condition is satisfied.

Sample Input 3

9012

Sample Output 3

Weak

Note that 0 follows 9.

Problem Statement

There are N types of beans, one bean of each type. The i-th type of bean has a deliciousness of A_i and a color of C_i. The beans are mixed and can only be distinguished by color.

You will choose one color of beans and eat one bean of that color. By selecting the optimal color, maximize the minimum possible deliciousness of the bean you eat.

Constraints

• 1 \leq N \leq 2 \times 10^{5}
• 1 \leq A_i \leq 10^{9}
• 1 \leq C_i \leq 10^{9}
• All input values are integers.

Sample Input 1

4
100 1
20 5
30 5
40 1

Sample Output 1

40

Note that beans of the same color cannot be distinguished from each other.

You can choose color 1 or color 5.

• There are two types of beans of color 1, with deliciousness of 100 and 40. Thus, the minimum deliciousness when choosing color 1 is 40.
• There are two types of beans of color 5, with deliciousness of 20 and 30. Thus, the minimum deliciousness when choosing color 5 is 20.

To maximize the minimum deliciousness, you should choose color 1, so print the minimum deliciousness in that case: 40.

Sample Input 2

10
68 3
17 2
99 2
92 4
82 4
10 3
100 2
78 1
3 1
35 4

Sample Output 2

35

Problem Statement

You are given a string S of length N consisting of 0 and 1.
Move the K-th 1-block from the beginning in S to immediately after the (K-1)-th 1-block, and print the resulting string.

It is guaranteed that S contains at least K 1-blocks.

Here is a more precise description.

• Let S_{l\ldots r} denote the substring of S from the l-th character through the r-th character.
• We define a substring S_{l\ldots r} of S to be a 1-block if it satisfies all of the following conditions:
  • S_l = S_{l+1} = \cdots = S_r = 1
  • l = 1 or S_{l-1} = 0
  • r = N or S_{r+1} = 0

• Suppose that all 1-blocks in S are S_{l_1\ldots r_1}, \ldots, S_{l_m\ldots r_m}, where l_1 < l_2 < \cdots < l_m.

  Then, we define the length N string T, obtained by moving the K-th 1-block to immediately after the (K-1)-th 1-block, as follows:

  • T_i = S_i for 1 \leq i \leq r_{K-1}
  • T_i = 1 for r_{K-1} + 1 \leq i \leq r_{K-1} + (r_K - l_K) + 1
  • T_i = 0 for r_{K-1} + (r_K - l_K) + 2 \leq i \leq r_K
  • T_i = S_i for r_K + 1 \leq i \leq N

Constraints

• 1 \leq N \leq 5 \times 10^5
• S is a string of length N consisting of 0 and 1.
• 2 \leq K
• S contains at least K 1-blocks.

Sample Input 1

15 3
010011100011001

Sample Output 1

010011111000001

S has four 1-blocks: from the 2nd to the 2nd character, from the 5th to the 7th character, from the 11th to the 12th character, and from the 15th to the 15th character.

Sample Input 2

10 2
1011111111

Sample Output 2

1111111110

Problem Statement

You are given a sequence of length N: A=(A_1,A_2,\dots,A_N). The following action on this sequence is called an operation.

• First, choose an integer i such that 1 \le i \le N.
• Next, choose and do one of the following.
  • Add 1 to A_i.
  • Subtract 1 from A_i.

Answer Q questions.
The i-th question is the following.

• Consider performing zero or more operations to change every element of A to X_i. Find the minimum number of operations required to do so.

Constraints

• All values in input are integers.
• 1 \le N,Q \le 2 \times 10^5
• 0 \le A_i \le 10^9
• 0 \le X_i \le 10^9

Sample Input 1

5 3
6 11 2 5 5
5
20
0

Sample Output 1

10
71
29

We have A=(6,11,2,5,5) and three questions in this input.

For the 1-st question, you can change every element of A to 5 in 10 operations as follows.

• Subtract 1 from A_1.
• Subtract 1 from A_2 six times.
• Add 1 to A_3 three times.

It is impossible to change every element of A to 5 in 9 or fewer operations.

For the 2-nd question, you can change every element of A to 20 in 71 operations.

For the 3-rd question, you can change every element of A to 0 in 29 operations.

Sample Input 2

10 5
1000000000 314159265 271828182 141421356 161803398 0 777777777 255255255 536870912 998244353
555555555
321654987
1000000000
789456123
0

Sample Output 2

3316905982
2811735560
5542639502
4275864946
4457360498

The output may not fit into 32-bit integers.

Problem Statement

There are N points on a two-dimensional plane. N is odd. The i-th point is at (x_i, y_i). All point coordinates are distinct.
Determine whether there exists a line passing through more than half of the N points, and if so, output it.
For any input satisfying the constraints, if a line satisfying the condition exists, it can be expressed as ax+by+c=0 using integers a,b,c with -10^{18} \leq a,b,c \leq 10^{18} (where (a,b,c) \neq (0,0,0)). Output these a,b,c.

Constraints

• 3 \leq N \leq 5 \times 10^5
• N is odd.
• -10^8 \leq x_i \leq 10^8
• -10^8 \leq y_i \leq 10^8
• If i \neq j, then (x_i, y_i) \neq (x_j, y_j).
• All input values are integers.

Sample Input 1

3
1 1
3 2
2 4

Sample Output 1

Yes
2 1 -8

The line 2x+y-8=0 passes through the 2nd and 3rd points, so it satisfies the condition.

Sample Input 2

5
5 2
1 3
2 6
4 4
5 4

Sample Output 2

No

No line satisfying the condition exists.

Sample Input 3

11
-9374372 85232388
-60705467 86198234
-7475320 80628487
98066347 -23868213
-12177678 85284287
30535572 -35358356
51324557 22410787
28854279 44658587
-28804873 82911971
65052073 8819187
-67744430 68365758

Sample Output 3

Yes
4655800 4702358 -344340416016346

Problem Statement

Given is a string S consisting of digits from 1 through 9.
From this string S, let us make a formula T by the following operations.

• Initially, let T=S.
• Choose a (possibly empty) set A of different integers where each element is between 1 and |S|-1 (inclusive).
• For each element x in descending order, do the following.
  • Insert a + between the x-th and (x+1)-th characters of T.

For example, when S= 1234 and A= \lbrace 2,3 \rbrace, we will have T= 12+3+4.

Consider evaluating all possible formulae T obtained by these operations. Find the sum, modulo 998244353, of the evaluations.

Constraints

• 1 \le |S| \le 2 \times 10^5
• S consists of 1, 2, 3, 4, 5, 6, 7, 8, and 9.

Sample Input 1

1234

Sample Output 1

1736

There are eight formulae that can be obtained as T: 1234, 123+4, 12+34, 12+3+4, 1+234, 1+23+4, 1+2+34, and 1+2+3+4.
The sum of the evaluations of these formulae is 1736.

Sample Input 2

1

Sample Output 2

1

S may have a length of 1, in which case the only possible choice for A is the empty set.

Sample Input 3

31415926535897932384626433832795

Sample Output 3

85607943

Be sure to find the sum modulo 998244353.