Problem Statement

Given a length-3 string S consisting of uppercase English letters, print Yes if S equals one of ACE, BDF, CEG, DFA, EGB, FAC, and GBD; print No otherwise.

Constraints

• S is a length-3 string consisting of uppercase English letters.

Sample Input 1

ABC

Sample Output 1

No

When S = ABC, S does not equal any of ACE, BDF, CEG, DFA, EGB, FAC, and GBD, so No should be printed.

Sample Input 2

FAC

Sample Output 2

Yes

Sample Input 3

XYX

Sample Output 3

No

Problem Statement

You are given a string s consisting of two kinds of characters, 0 and 1. Print the string obtained by replacing 0 with 1 and 1 with 0 in s.

Constraints

• The length of s is between 1 and 10, inclusive.
• s consists of two kinds of characters, 0 and 1.

Sample Input 1

01

Sample Output 1

10

The 1-st character of s is 1, so the 1-st character to print is 0. The 2-nd character of s is 0, so the 2-nd character to print is 1.

Sample Input 2

1011

Sample Output 2

0100

Sample Input 3

100100001

Sample Output 3

011011110

Problem Statement

You are given three strings S_1, S_2, S_3 consisting of lowercase English letters, and a string T consisting of 1, 2, 3.

Concatenate the three strings according to the characters in T and print the resulting string. Formally, conform to the following instructions.

• For each integer i such that 1 \leq i \leq |T|, let the string s_i be defined as follows:
  • S_1, if the i-th character of T is 1;
  • S_2, if the i-th character of T is 2;
  • S_3, if the i-th character of T is 3.
• Concatenate the strings s_1, s_2, \dots, s_{|T|} in this order and print the resulting string.

Constraints

• 1 \leq |S_1|, |S_2|, |S_3| \leq 10
• 1 \leq |T| \leq 1000
• S_1, S_2, and S_3 consist of lowercase English letters.
• T consists of 1, 2, and 3.

Sample Input 1

mari
to
zzo
1321

Sample Output 1

marizzotomari

We have s_1 = mari, s_2 = zzo, s_3 = to, s_4 = mari. Concatenate these and print the resulting string: marizzotomari.

Sample Input 2

abra
cad
abra
123

Sample Output 2

abracadabra

Sample Input 3

a
b
c
1

Sample Output 3

a

Problem Statement

There are N people numbered 1, 2, \dots, N in the xy-plane. Person i is at the coordinates (X_i, Y_i).
K of these people, Persons A_1, A_2, \dots, A_K, will receive lights of the same strength.
When a person at coordinates (x, y) has a light of strength R, it lights up the interior of a circle of radius R centered at (x, y) (including the boundary).
Find the minimum strength of the lights needed for every person to be lit by at least one light.

Constraints

• All values in input are integers.
• 1 \le K < N \le 1000
• 1 \le A_1 < A_2 < \dots < A_K \le N
• |X_i|,|Y_i| \le 10^5
• (X_i,Y_i) \neq (X_j,Y_j), if i \neq j.

Sample Input 1

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

Sample Output 1

2.23606797749978969

This input contains four people. Among them, Persons 2 and 3 will have lights.
Every person will be lit by at least one light if R \ge \sqrt{5} \approx 2.236068.

Sample Input 2

2 1
2
-100000 -100000
100000 100000

Sample Output 2

282842.712474619009

Sample Input 3

8 3
2 6 8
-17683 17993
93038 47074
58079 -57520
-41515 -89802
-72739 68805
24324 -73073
71049 72103
47863 19268

Sample Output 3

130379.280458974768

Problem Statement

Given is a string S consisting of lowercase English letters. Determine whether adding some number of a's (possibly zero) at the beginning of S can make it a palindrome.

Here, a string of length N, A=A_1A_2\ldots A_N, is said to be a palindrome when A_i=A_{N+1-i} for every 1\leq i\leq N.

Constraints

• 1 \leq \lvert S \rvert \leq 10^6
• S consists of lowercase English letters.

Sample Input 1

kasaka

Sample Output 1

Yes

By adding one a at the beginning of kasaka, we have akasaka, which is a palindrome, so Yes should be printed.

Sample Input 2

atcoder

Sample Output 2

No

Adding any number of a's at the beginning of atcoder does not make it a palindrome.

Sample Input 3

php

Sample Output 3

Yes

php itself is a palindrome. Adding zero a's at the beginning of S is allowed, so Yes should be printed.

Problem Statement

In the xy-plane, we have N points numbered 1 through N.
Point i is at the coordinates (X_i,Y_i). Any two different points are at different positions.
Find the number of ways to choose three of these N points so that connecting the chosen points with segments results in a triangle with a positive area.

Constraints

• All values in input are integers.
• 3 \le N \le 300
• -10^9 \le X_i,Y_i \le 10^9
• (X_i,Y_i) \neq (X_j,Y_j) if i \neq j.

Sample Input 1

4
0 1
1 3
1 1
-1 -1

Sample Output 1

3

The figure below illustrates the points.

There are three ways to choose points that form a triangle: \{1,2,3\},\{1,3,4\},\{2,3,4\}.

Sample Input 2

20
224 433
987654321 987654321
2 0
6 4
314159265 358979323
0 0
-123456789 123456789
-1000000000 1000000000
124 233
9 -6
-4 0
9 5
-7 3
333333333 -333333333
-9 -1
7 -10
-1 5
324 633
1000000000 -1000000000
20 0

Sample Output 2

1124

Problem Statement

Takahashi is having trouble with deciding a username for a service. Write a code to help him.

Find a string X that satisfies all of the following conditions:

• X is obtained by the following procedure:
  • Let S_1', S_2', \ldots,S_N' be a permutation of S_1, S_2, \ldots,S_N. Let X be the concatenation of S_1', (1 or more copies of _), S_2', (1 or more copies of _), \ldots, (1 or more copies of _), and S_N', in this order.
• The length of X is between 3 and 16, inclusive.
• X does not coincide with any of M strings T_1,T_2,\ldots,T_M.

If there is no X that satisfies all of the conditions, print -1 instead.

Constraints

• 1 \leq N \leq 8
• 0 \leq M \leq 10^5
• N and M are integers.
• 1 \leq |S_i| \leq 16
• N-1+\sum{|S_i|} \leq 16
• S_i \neq S_j if i \neq j.
• S_i is a string consisting of lowercase English letters.
• 3 \leq |T_i| \leq 16
• T_i \neq T_j if i \neq j.
• T_i is a string consisting of lowercase English letters and _.

Sample Input 1

1 1
chokudai
chokudai

Sample Output 1

-1

The only string that satisfies the first and second conditions is X= chokudai, but it coincides with T_1.
Thus, there is no X that satisfies all of the conditions, so -1 should be printed.

Sample Input 2

2 2
choku
dai
chokudai
choku_dai

Sample Output 2

dai_choku

Strings like choku__dai (which has two _'s between choku and dai) also satisfy all of the conditions.

Sample Input 3

2 2
chokudai
atcoder
chokudai_atcoder
atcoder_chokudai

Sample Output 3

-1

chokudai__atcoder and atcoder__chokudai (which have two _'s between chokudai and atcoder) have a length of 17, which violates the second condition.

Sample Input 4

4 4
ab
cd
ef
gh
hoge
fuga
____
_ab_cd_ef_gh_

Sample Output 4

ab__ef___cd_gh

The given T_i may contain a string that cannot be obtained by the procedure described in the first condition.

Problem Statement

The Republic of AtCoder has N cities, called City 1, City 2, \ldots, City N. Initially, there was a bidirectional road between every pair of different cities, but M of these roads have become unusable due to deterioration over time. More specifically, for each 1\leq i \leq M, the road connecting City U_i and City V_i has become unusable.

Takahashi will go for a K-day trip that starts and ends in City 1. Formally speaking, a K-day trip that starts and ends in City 1 is a sequence of K+1 cities (A_0, A_1, \ldots, A_K) such that A_0=A_K=1 holds and for each 0\leq i\leq K-1, A_i and A_{i+1} are different and there is still a usable road connecting City A_i and City A_{i+1}.

Print the number of different K-day trips that start and end in City 1, modulo 998244353. Here, two K-day trips (A_0, A_1, \ldots, A_K) and (B_0, B_1, \ldots, B_K) are said to be different when there exists an i such that A_i\neq B_i.

Constraints

• 2 \leq N \leq 5000
• 0 \leq M \leq \min\left( \frac{N(N-1)}{2},5000 \right)
• 2 \leq K \leq 5000
• 1 \leq U_i<V_i \leq N
• All pairs (U_i, V_i) are pairwise distinct.
• All values in input are integers.

Sample Input 1

3 1 4
2 3

Sample Output 1

4

There are four different trips as follows.

• (1,2,1,2,1)
• (1,2,1,3,1)
• (1,3,1,2,1)
• (1,3,1,3,1)

No other trip is valid, so we should print 4.

Sample Input 2

3 3 3
1 2
1 3
2 3

Sample Output 2

0

No road remains usable, so there is no valid trip.

Sample Input 3

5 3 100
1 2
4 5
2 3

Sample Output 3

428417047

Problem Statement

There are apple trees lined up on a number line, and N apples fall from the trees.
Specifically, for each 1\leq i\leq N, an apple falls at coordinate X_i at time T_i.

Takahashi has a basket with durability D and length W, and he can take the following action exactly once.

Choose positive integers S and L. He sets up the basket to cover the range L-0.5\leq x\leq L+W-0.5 at time S-0.5, and retrieves it at time S+D-0.5. He gets all the apples that fell into the range covered by the basket between the time it was set up and the time it was retrieved.

He cannot move the basket once it has been set up, nor can he set it up again once it has been retrieved.
Find the maximum number of apples that he can get.

Constraints

• 1 \leq N\leq 2\times 10^5
• 1 \leq D\leq 2\times 10^5
• 1 \leq W\leq 2\times 10^5
• 1 \leq T_i\leq 2\times 10^5
• 1 \leq X_i\leq 2\times 10^5
• All pairs (T_i,X_i) are different.
• All input values are integers.

Sample Input 1

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

Sample Output 1

5

If Takahashi chooses S=3 and L=2, he will set up the basket to cover the range 1.5\leq x\leq 4.5 from time 2.5 to 6.5. Then, he gets the following five apples:

• The apple that falls at coordinate X_2=4 at time T_2=3
• The apple that falls at coordinate X_3=4 at time T_3=6
• The apple that falls at coordinate X_4=2 at time T_4=5
• The apple that falls at coordinate X_5=2 at time T_5=4
• The apple that falls at coordinate X_6=3 at time T_6=4

There is no way to get six or more apples, so print 5.