Problem Statement

N people labeled 1,2,\dots,N took an exam, and person i scored A_i points.
Only those who scored at least L points pass this exam.
Determine how many people out of the N have passed the exam.

Constraints

• All input values are integers.
• 1 \le N \le 100
• 1 \le L \le 1000
• 0 \le A_i \le 1000

Sample Input 1

5 60
60 20 100 90 40

Sample Output 1

3

Five people took the exam. You need to score at least 60 points to pass.

• Person 1 scored 60 points, so they passed.
• Person 2 scored 20 points, so they did not pass.
• Person 3 scored 100 points, so they passed.
• Person 4 scored 90 points, so they passed.
• Person 5 scored 40 points, so they did not pass.

From the above, we can see that three people have passed.

Sample Input 2

4 80
79 78 77 76

Sample Output 2

0

There may be cases no one has passed.

Sample Input 3

10 50
31 41 59 26 53 58 97 93 23 84

Sample Output 3

6

Problem Statement

You are given N integers A _ 1,A _ 2,\ldots,A _ N.

If their values are all equal, print Yes; otherwise, print No.

Constraints

• 2\leq N\leq100
• 1\leq A _ i\leq100\ (1\leq i\leq N)
• All input values are integers.

Sample Input 1

3
3 2 4

Sample Output 1

No

We have A _ 1\neq A _ 2, so you should print No.

Sample Input 2

4
3 3 3 3

Sample Output 2

Yes

We have A _ 1=A _ 2=A _ 3=A _ 4, so you should print Yes.

Sample Input 3

10
73 8 55 26 97 48 37 47 35 55

Sample Output 3

No

Problem Statement

How many triples of non-negative integers (a, b, c) satisfy a+b+c \leq S and a \times b \times c \leq T?

Constraints

• 0 \leq S \leq 100
• 0 \leq T \leq 10000
• S and T are integers.

Sample Input 1

1 0

Sample Output 1

4

The triples (a,b,c) satisfying the conditions are (0,0,0), (0,0,1), (0,1,0), and (1,0,0) ― there are four of them.

Sample Input 2

2 5

Sample Output 2

10

Sample Input 3

10 10

Sample Output 3

213

Sample Input 4

30 100

Sample Output 4

2471

Problem Statement

You are given N integers A_1, A_2, \ldots, A_N. Find the largest among those integers that are not the largest.

The constraints of this problem guarantee that the answer exists.

Constraints

• 2 \leq N \leq 100
• 1 \leq A_i \leq 100
• It is not the case that all A_1, A_2, \ldots, A_N are equal.
• All input values are integers.

Sample Input 1

5
2 1 3 3 2

Sample Output 1

2

The largest integer among 2,1,3,3,2 is 3.

The integers that are not 3 among 2,1,3,3,2 are 2,1,2, among which the largest is 2.

Sample Input 2

4
4 3 2 1

Sample Output 2

3

Sample Input 3

8
22 22 18 16 22 18 18 22

Sample Output 3

18

Problem Statement

You are given a string S = S_1S_2\ldots S_N of length N consisting of lowercase English letters.

Additionally, you are given Q queries about the string S. For i = 1, 2, \ldots, Q, the i-th query is represented by two integers l_i, r_i and asks the following.

In the substring S_{l_i}S_{l_i+1}\ldots S_{r_i} of S, which ranges from the l_i-th to the r_i-th character, how many places are there where the same lowercase English letter occurs twice in a row? In other words, how many integers p satisfy l_i \leq p \leq r_i-1 and S_p = S_{p+1}?

Print the answer for each of the Q queries.

Constraints

• N and Q are integers.
• 1 \leq N, Q \leq 3 \times 10^5
• S is a string of length N consisting of lowercase English letters.
• l_i and r_i are integers.
• 1 \leq l_i \leq r_i \leq N

Sample Input 1

11 4
mississippi
3 9
4 10
4 6
7 7

Sample Output 1

2
2
0
0

The answers to the four queries are as follows.

• For the first query, S_3S_4\ldots S_9 = ssissip has two places where the same lowercase English letter occurs twice in a row: S_3S_4 = ss and S_6S_7 = ss.
• For the second query, S_4S_5\ldots S_{10} = sissipp has two places where the same lowercase English letter occurs twice in a row: S_6S_7 = ss and S_9S_{10} = pp.
• For the third query, S_4S_5S_6 = sis has zero places where the same lowercase English letter occurs twice in a row.
• For the fourth query, S_7 = s has zero places where the same lowercase English letter occurs twice in a row.

Sample Input 2

5 1
aaaaa
1 5

Sample Output 2

4

S_1S_2\ldots S_5 = aaaaa has four places where the same lowercase English letter occurs twice in a row: S_1S_2 = aa, S_2S_3 = aa, S_3S_4 = aa, and S_4S_5 = aa.

Problem Statement

You are given a positive integer N.
Find the number of quadruples of positive integers (A,B,C,D) such that AB + CD = N.

Under the constraints of this problem, it can be proved that the answer is at most 9 \times 10^{18}.

Constraints

• 2 \leq N \leq 2 \times 10^5
• N is an integer.

Sample Input 1

4

Sample Output 1

8

Here are the eight desired quadruples.

• (A,B,C,D)=(1,1,1,3)
• (A,B,C,D)=(1,1,3,1)
• (A,B,C,D)=(1,2,1,2)
• (A,B,C,D)=(1,2,2,1)
• (A,B,C,D)=(1,3,1,1)
• (A,B,C,D)=(2,1,1,2)
• (A,B,C,D)=(2,1,2,1)
• (A,B,C,D)=(3,1,1,1)

Sample Input 2

292

Sample Output 2

10886

Sample Input 3

19876

Sample Output 3

2219958

Problem Statement

You are given a string S consisting of A, B, C.

Let S^{(0)}:=S. For i=1,2,3,\ldots, let S^{(i)} be the result of simultaneously replacing the characters of S^{(i-1)} as follows: A → BC, B → CA, C → AB.

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

• Print the k_i-th character from the beginning of S^{(t_i)}.

Constraints

• S is a string of length between 1 and 10^5 (inclusive) consisting of A, B, C.
• 1 \leq Q \leq 10^5
• 0 \leq t_i \leq 10^{18}
• 1 \leq k_i \leq \min(10^{18}, the length of S^{(t_i)})
• Q, t_i, k_i are integers.

Sample Input 1

ABC
4
0 1
1 1
1 3
1 6

Sample Output 1

A
B
C
B

We have S^{(0)}=ABC, S^{(1)}=BCCAAB.

Thus, the answers to the queries are A, B, C, B in the given order.

Sample Input 2

CBBAACCCCC
5
57530144230160008 659279164847814847
29622990657296329 861239705300265164
509705228051901259 994708708957785197
176678501072691541 655134104344481648
827291290937314275 407121144297426665

Sample Output 2

A
A
C
A
A

Problem Statement

Takahashi is at the origin of a two-dimensional plane.
Takahashi will repeat teleporting N times. In each teleportation, he makes one of the following moves:

• Move from the current coordinates (x,y) to (x+A,y+B)
• Move from the current coordinates (x,y) to (x+C,y+D)
• Move from the current coordinates (x,y) to (x+E,y+F)

There are obstacles on M points (X_1,Y_1),\ldots,(X_M,Y_M) on the plane; he cannot teleport to these coordinates.

How many paths are there resulting from the N teleportations? Find the count modulo 998244353.

Constraints

• 1 \leq N \leq 300
• 0 \leq M \leq 10^5
• -10^9 \leq A,B,C,D,E,F \leq 10^9
• (A,B), (C,D), and (E,F) are distinct.
• -10^9 \leq X_i,Y_i \leq 10^9
• (X_i,Y_i)\neq(0,0)
• (X_i,Y_i) are distinct.
• All values in input are integers.

Sample Input 1

2 2
1 1 1 2 1 3
1 2
2 2

Sample Output 1

5

The following 5 paths are possible:

• (0,0)\to(1,1)\to(2,3)
• (0,0)\to(1,1)\to(2,4)
• (0,0)\to(1,3)\to(2,4)
• (0,0)\to(1,3)\to(2,5)
• (0,0)\to(1,3)\to(2,6)

Sample Input 2

10 3
-1000000000 -1000000000 1000000000 1000000000 -1000000000 1000000000
-1000000000 -1000000000
1000000000 1000000000
-1000000000 1000000000

Sample Output 2

0

Sample Input 3

300 0
0 0 1 0 0 1

Sample Output 3

292172978

Problem Statement

You are given N strings S _ 1,S _ 2,\ldots,S _ N. S _ i\ (1\leq i\leq N) is a non-empty string of length at most 10 consisting of lowercase English letters, and the strings are pairwise distinct.

Taro the First and Jiro the Second play a word-chain game. In this game, the two players take alternating turns, with Taro the First going first. In each player's turn, the player chooses an integer i\ (1\leq i\leq N), which should satisfy the following two conditions:

• i is different from any integer chosen by the two players so far since the game started;
• the current turn is the first turn of the game, or the last character of S_j equals the first character of S_i, where j is the last integer chosen.

The player who is unable to choose a conforming i loses; the other player wins.

Determine which player will win if the two players play optimally.

Constraints

• 1 \leq N \leq 16
• N is an integer.
• S _ i\ (1\leq i\leq N) is a non-empty string of length at most 10 consisting of lowercase English letters.
• S _ i\neq S _ j\ (1\leq i\lt j\leq N)

Sample Input 1

6
enum
float
if
modint
takahashi
template

Sample Output 1

First

For example, the game progresses as follows. Note that the two players may not be playing optimally in this example.

• Taro the First chooses i=3. S _ i=if.
• Jiro the Second chooses i=2. S _ i=float, and the last character of if equals the first character of float.
• Taro the First chooses i=5. S _ i=takahashi, and the last character of float equals the first character of takahashi.
• Jiro the Second is unable to choose i\neq2,3,5 such that S _ i starts with i, so he loses.

In this case, Taro the First wins.

Sample Input 2

10
catch
chokudai
class
continue
copy
exec
havoc
intrinsic
static
yucatec

Sample Output 2

Second

Sample Input 3

16
mnofcmzsdx
lgeowlxuqm
ouimgdjxlo
jhwttcycwl
jbcuioqbsj
mdjfikdwix
jhvdpuxfil
peekycgxco
sbvxszools
xuuqebcrzp
jsciwvdqzl
obblxzjhco
ptobhnpfpo
muizaqtpgx
jtgjnbtzcl
sivwidaszs

Sample Output 3

First