Problem Statement

In a certain programming contest, T-shirts are awarded to participants according to the following rules.

• All participants who ranked A-th or higher get a T-shirt.
• Additionally, from the participants who ranked between (A+1)-th and B-th (inclusive), C participants chosen uniformly at random get a T-shirt.

There were 1000 participants in this contest, and all of them got different ranks.
Iroha-chan, who participated in this contest, ranked X-th.
Find the probability that she gets a T-shirt.

Constraints

• All values in input are integers.
• 1 \le A < B \le 1000
• 1 \le C \le B-A
• 1 \le X \le 1000

Sample Input 1

30 500 20 103

Sample Output 1

0.042553191489

Iroha-chan ranked 103-rd.
She will get a T-shirt if she is among the 20 participants chosen uniformly at random from the 470 participants who ranked between 31-st and 500-th, which happens with probability \frac{20}{470}=0.04255319\dots.

Sample Input 2

50 500 100 1

Sample Output 2

1.000000000000

Iroha-chan ranked 1-st. This time, she is guaranteed to get a T-shirt.

Sample Input 3

1 2 1 1000

Sample Output 3

0.000000000000

Iroha-chan ranked 1000-th. This time, she will never get a T-shirt.

Problem Statement

You are given a non-empty string S consisting of uppercase and lowercase English letters. Determine whether the following condition is satisfied:

• The first character of S is uppercase, and all other characters are lowercase.

Constraints

• 1 \leq |S| \leq 100 (|S| is the length of the string S.)
• Each character of S is an uppercase or lowercase English letter.

Sample Input 1

Capitalized

Sample Output 1

Yes

The first character C of Capitalized is uppercase, and all other characters apitalized are lowercase, so you should print Yes.

Sample Input 2

AtCoder

Sample Output 2

No

AtCoder contains an uppercase letter C that is not at the beginning, so you should print No.

Sample Input 3

yes

Sample Output 3

No

The first character y of yes is not uppercase, so you should print No.

Sample Input 4

A

Sample Output 4

Yes

Problem Statement

There are N players numbered 1 to N, who have played a round-robin tournament. For every match in this tournament, one player won and the other lost.

The results of the matches are given as N strings S_1,S_2,\ldots,S_N of length N each, in the following format:

• If i\neq j, the j-th character of S_i is o or x. o means that player i won against player j, and x means that player i lost to player j.

• If i=j, the j-th character of S_i is -.

The player with more wins ranks higher. If two players have the same number of wins, the player with the smaller player number ranks higher. Report the player numbers of the N players in descending order of rank.

Constraints

• 2\leq N\leq 100
• N is an integer.
• S_i is a string of length N consisting of o, x, and -.
• S_1,\ldots,S_N conform to the format described in the problem statement.

Sample Input 1

3
-xx
o-x
oo-

Sample Output 1

3 2 1

Player 1 has 0 wins, player 2 has 1 win, and player 3 has 2 wins. Thus, the player numbers in descending order of rank are 3,2,1.

Sample Input 2

7
-oxoxox
x-xxxox
oo-xoox
xoo-ooo
ooxx-ox
xxxxx-x
oooxoo-

Sample Output 2

4 7 3 1 5 2 6

Both players 4 and 7 have 5 wins, but player 4 ranks higher because their player number is smaller.

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

You are given a positive integer D.

Find the minimum value of |x^2+y^2-D| for non-negative integers x and y.

Constraints

• 1\leq D \leq 2\times 10^{12}
• All input values are integers.

Sample Input 1

21

Sample Output 1

1

For x=4 and y=2, we have |x^2+y^2-D| = |16+4-21|=1.

There are no non-negative integers x and y such that |x^2+y^2-D|=0, so the answer is 1.

Sample Input 2

998244353

Sample Output 2

0

Sample Input 3

264428617

Sample Output 3

32

Problem Statement

You are given an integer X. The following action on this integer is called an operation.

• Choose and do one of the following.
  • Add 1 to X.
  • Subtract 1 from X.

The terms in the arithmetic progression S with N terms whose initial term is A and whose common difference is D are called good numbers.
Consider performing zero or more operations to make X a good number. Find the minimum number of operations required to do so.

Constraints

• All values in input are integers.
• -10^{18} \le X,A \le 10^{18}
• -10^6 \le D \le 10^6
• 1 \le N \le 10^{12}

Sample Input 1

6 2 3 3

Sample Output 1

1

Since A=2,D=3,N=3, we have S=(2,5,8).
You can subtract 1 from X once to make X=6 a good number.
It is impossible to make X good in zero operations.

Sample Input 2

0 0 0 1

Sample Output 2

0

We might have D=0. Additionally, no operation might be required.

Sample Input 3

998244353 -10 -20 30

Sample Output 3

998244363

Sample Input 4

-555555555555555555 -1000000000000000000 1000000 1000000000000

Sample Output 4

444445

Problem Statement

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

We perform the following operation on S 10^{100} times:

• First, create a string T by changing uppercase letters in S to lowercase, and lowercase letters to uppercase.
• Then, concatenate S and T in this order to form a new S.

Answer Q queries. The i-th query is as follows:

• Find the K_i-th character from the beginning of S after all operations are completed.

Constraints

• S is a string consisting of uppercase and lowercase English letters, with length between 1 and 2 \times 10^5, inclusive.
• Q and K_i are integers.
• 1 \le Q \le 2 \times 10^5
• 1 \le K_i \le 10^{18}

Sample Input 1

aB
16
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

Sample Output 1

a B A b A b a B A b a B a B A b

Before the operations, S = aB.

• After performing the operation once on aB, it becomes aBAb.
• After performing the operation twice on aB, it becomes aBAbAbaB.
• \dots

After performing the operation 10^{100} times, S = aBAbAbaBAbaBaBAb...

Sample Input 2

qWeRtYuIoP
8
1 1 2 3 5 8 13 21

Sample Output 2

q q W e t I E Q

Sample Input 3

AnUoHrjhgfLMcDIpzxXmEWPwBZvbKqQuiJTtFSlkNGVReOYCdsay
5
1000000000000000000 123456789 1 987654321 999999999999999999

Sample Output 3

K a A Z L

Problem Statement

You are given a tree with NK vertices. The vertices are numbered 1,2,\dots,NK, and the i-th edge (i=1,2,\dots,NK-1) connects vertices u_i and v_i bidirectionally.

Determine whether this tree can be decomposed into N paths, each of length K. More precisely, determine whether there exists an N \times K matrix P satisfying the following:

• P_{1,1}, \dots, P_{1,K}, P_{2,1}, \dots, P_{N,K} is a permutation of 1,2,\dots,NK.
• For each i=1,2,\dots,N and j=1,2,\dots,K-1, there is an edge connecting vertices P_{i,j} and P_{i,j+1}.

Constraints

• 1 \leq N
• 1 \leq K
• NK \leq 2 \times 10^5
• 1 \leq u_i < v_i \leq NK
• The given graph is a tree.
• All input values are integers.

Sample Input 1

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

Sample Output 1

Yes

It can be decomposed into a path with vertices 1,2, a path with vertices 3,4, and a path with vertices 5,6.

Sample Input 2

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

Sample Output 2

No

Problem Statement

You are given two sequences of N numbers: A=(A_1,A_2,\ldots,A_N) and B=(B_1,B_2,\ldots,B_N).

Takahashi can repeat the following operation any number of times (possibly zero).

Choose three pairwise distinct integers i, j, and k between 1 and N.
Swap the i-th and j-th elements of A, and swap the i-th and k-th elements of B.

If there is a way for Takahashi to repeat the operation to make A and B equal, print Yes; otherwise, print No.
Here, A and B are said to be equal when, for every 1\leq i\leq N, the i-th element of A and that of B are equal.

Constraints

• 3 \leq N \leq 2\times 10^5
• 1\leq A_i,B_i\leq N
• All values in the input are integers.

Sample Input 1

3
1 2 1
1 1 2

Sample Output 1

Yes

Performing the operation once with (i,j,k)=(1,2,3) swaps A_1 and A_2, and swaps B_1 and B_3,
making both A and B equal to (2,1,1). Thus, you should print Yes.

Sample Input 2

3
1 2 2
1 1 2

Sample Output 2

No

There is no way to perform the operation to make A and B equal, so you should print No.

Sample Input 3

5
1 2 3 2 1
3 2 2 1 1

Sample Output 3

Yes

Sample Input 4

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

Sample Output 4

No