Problem Statement

Takahashi went shopping at a supermarket. The supermarket has A onions and B potatoes in stock.

Takahashi is so thoughtful that, for each vegetable, if buying the desired quantity would empty the stock, he decides not buying it.

Can Takahashi buy C onions and D potatoes?

Constraints

• 1 \leq A,B,C,D \leq 100
• All input values are integers.

Sample Input 1

3 5 4 2

Sample Output 1

No

They sells only three onions, so he cannot buy four.

Sample Input 2

30 10 6 10

Sample Output 2

No

They sells ten potatoes, but buying ten will empty the stock, so he decides not buying them.

Sample Input 3

100 100 1 1

Sample Output 3

Yes

Problem Statement

You are given three integers satisfying A+C=B or B+C=A.
Among these two equations, let x+C=y be the one that is satisfied.
Print x,y,C in this equation in the format x -> y (C).
Here, C must be printed as a signed integer.

For example:

• If A=1000, B=1050, C=50, we have 1000+50=1050, so print 1000 -> 1050 (+50).
• If A=1000, B=1050, C=-50, we have 1050+(-50)=1000, so print 1050 -> 1000 (-50).

Constraints

• All input values are integers.
• 0 \le A,B \le 5000
• -5000 \le C \le 5000
• C \neq 0
• A+C=B or B+C=A.

Sample Input 1

1000 1050 50

Sample Output 1

1000 -> 1050 (+50)

Sample Input 2

1000 1050 -50

Sample Output 2

1050 -> 1000 (-50)

Sample Input 3

1234 1111 -123

Sample Output 3

1234 -> 1111 (-123)

Sample Input 4

3000 2500 500

Sample Output 4

2500 -> 3000 (+500)

Problem Statement

You are given integers N and K, and a length-N string S.

You are scheduling a meeting.

Whether you can set a meeting on each day is described by a string S. If the i-th character of S is o, you can set a meeting on day i; if it is x, you cannot.

The meeting was scheduled on day K, but it was postponed.

You now need to reschedule it to the closest available day on or after day (K + 1).

Find the new day for the meeting. It is guaranteed that you can always set the meeting by day N.

Constraints

• 2\le N\le 10^3
• 1\le K\le N
• N and K are integers.
• S is a string of length N, consisting of o and x.
• The K-th character of S is o.
• There is an o at the (K+1)-th or later position of S.

Sample Input 1

6 2
ooxoxo

Sample Output 1

4

You can set the meeting on days 1,2,4,6. On or after day 2+1=3, the closest to day 2 is day 4, so print 4.

Sample Input 2

5 4
ooooo

Sample Output 2

5

Sample Input 3

11 6
ooxxxoxooxx

Sample Output 3

8

Problem Statement

You are given a grid with H rows and W columns. Each cell contains a lowercase English letter; the letter in the cell at row i (counted from the top) and column j (from the left) is the j-th character of the given string S_i.

Given lowercase English letters c_1 and c_2, determine if the grid has a pair of cells that share a side, containing letters c_1 and c_2.

More precisely, determine if there is a tuple of positive integers (h_1,w_1,h_2,w_2) such that:

• 1\le h_1,h_2\le H
• 1\le w_1,w_2\le W
• The cell in row h_1 and column w_1 contains the letter c_1.
• The cell in row h_2 and column w_2 contains the letter c_2.
• |h_1-h_2|+|w_1-w_2|=1

Constraints

• 1\le H,W\le 10
• H and W are integers.
• c_1 and c_2 are lowercase English letters.
• Each of S_1,S_2,\ldots,S_H is a string of length W, consisting of lowercase English letters.

Sample Input 1

3 3 a t
abc
xtc
qad

Sample Output 1

Yes

The cell in row 3 and column 2 from the left contains a; the cell in row 2 and column 2 contains t. These cells share a side, so print Yes.

Sample Input 2

4 3 x r
xxx
xxb
kkr
rrr

Sample Output 2

No

There are no adjacent cells with x and r, so print No.

Sample Input 3

5 5 n x
iaamg
krwwu
nzyxc
sgrnt
mmjip

Sample Output 3

Yes

Problem Statement

Given a sequence of N pairwise-distinct irreducible fractions \displaystyle \left(\frac{A_1}{B_1}, \frac{A_2}{B_2}, \dots, \frac{A_N}{B_N}\right), sort it in ascending order.

Constraints

• 1 \leq N \leq 10^3
• 1 \leq A_i \leq 10^{18}
• 1 \leq B_i \leq 10^{18}
• \gcd(A_i, B_i) = 1
• (A_i,B_i) \neq (A_j,B_j) if i \neq j.
• All input values are integers.

Sample Input 1

3
2 3
1 2
3 5

Sample Output 1

1 2
3 5
2 3

Since \displaystyle \frac{1}{2} \lt \frac{3}{5} \lt \frac{2}{3}, the sorted sequence is \displaystyle \left(\frac{1}{2}, \frac{3}{5}, \frac{2}{3} \right).

Sample Input 2

5
1 5
1 7
6 5
9 8
9 4

Sample Output 2

1 7
1 5
9 8
6 5
9 4

Sample Input 3

10
39 83
93 70
5 92
81 67
30 53
57 5
91 58
21 85
81 34
37 38

Sample Output 3

5 92
21 85
39 83
30 53
37 38
81 67
93 70
91 58
81 34
57 5

Problem Statement

There are N people.

Person i's best friend is person A_i. If person i is person j's best friend, then it is also guaranteed that person j is person i's best friend.

Person i loves person B_i.

Find the number of triples of integers (i,j,k) such that:

• 1 \leq i < j \leq N.
• 1 \leq k \leq N.
• Persons i and j are best friends of each other.
• Persons i and j both love person k.

Constraints

• 2 \leq N \leq 2\times 10^5
• N is even.
• 1 \leq A_i,B_i \leq N
• A_i \neq i
• If A_i=j, then A_j=i.
• B_i \neq i
• All input values are integers.

Sample Input 1

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

Sample Output 1

1

Only (2,3,1) is eligible.

Sample Input 2

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

Sample Output 2

2

Tuples (1,9,7),(4,5,8) are eligible.

Problem Statement

You are given a sequence A of length N.
Sequence B is an infinite-time repetition of A.
More precisely, define B_i = A_{((i-1)\ {\rm mod}\ N) + 1} for all integers i, where p\ {\rm mod}\ q denotes the remainder when p is divided by q.

Answer the following Q queries. The i-th query is:

• Find the sum of the L_i-th through R_i-th terms of B.

Constraints

• All input values are integers.
• 1 \le N \le 2 \times 10^5
• 1 \le Q \le 2 \times 10^5
• 0 \le A_i \le 10^6
• 1 \le L_i \le R_i \le 10^{12}

Sample Input 1

8 5
3 1 4 1 5 9 2 6
3 7
6 10
1 16
4 21
1 1000000000000

Sample Output 1

21
21
62
68
3875000000000

We have B=(3,1,4,1,5,9,2,6,3,1,4,1,5,9,2,6,\dots).

This input contains five queries. The first two are as follows.

• For the 1-st query, find the sum of the 3-rd through 7-th terms: 4+1+5+9+2 = 21.
• For the 2-nd query, find the sum of the 6-th through 10-th terms: 9+2+6+3+1=21.

Problem Statement

You are given an integer N, and an integer sequence A=(A_1,A_2,\ldots,A_N) of length N.

A sandwich triple is an integer triple (i,j,k) such that:

• 1\le i < j < k \le N; and
• A_i=A_k\neq A_j.

How many sandwich triples are there?

Constraints

• 3\le N\le 2\times 10^5
• 1\le A_i\le 10^9
• All input values are integers.

Sample Input 1

5
2 5 2 2 5

Sample Output 1

4

The sandwich triples are (i,j,k)=(1,2,3),(1,2,4),(2,3,5),(2,4,5).

Sample Input 2

5
4 4 4 4 4

Sample Output 2

0

No choice of (i,j,k) satisfies A_i=A_k\neq A_j.

Sample Input 3

10
2 2 6 4 4 6 6 2 3 2

Sample Output 3

27

Problem Statement

A string shop sells N strings. The i-th string is S_i and sold for X_i yen (the currency in Japan).

You will buy zero or more strings for a total of at most Y yen. Find the maximum possible number of distinct letters in the bought strings.

Constraints

• 1\leq N \leq 18
• 1 \leq Y \leq 10^9
• S_i is a string of length between 1 and 100, inclusive, consisting of lowercase English letters.
• 1 \leq X_i \leq 10^9
• All input numbers are integers.

Sample Input 1

4 900
apple 300
orange 200
lemon 500
pomegranate 1000

Sample Output 1

8

If you buy the 2-nd and 3-rd strings for a total of 700 yen, they will contain eight distinct letters: a, e, g, l, m, n, o, r.

Sample Input 2

2 200
melon 100
lemon 100

Sample Output 2

5

If you buy the 1-st and 2-nd strings for a total of 200 yen, they will contain five distinct letters: e, l, m, n, o.

Sample Input 3

1 1
abcdefghijklmnopqrstuvwxyz 10000

Sample Output 3

0

You may not be able to buy any strings.

Problem Statement

Company A has N employees.

One day, employee i arrived at work at time S_i and left there at time T_i.

For each i, find how many other employees met employee i at the office on that day.

Here, employees i and j are considered to have met each other if and only if they were at the office at any moment, even if one arrived at work exactly when the other left there.

Constraints

• 2 \leq N \leq 2\times 10^5
• 1 \leq S_i \leq T_i \leq 2\times 10^5
• All input values are integers.

Sample Input 1

4
1 10
5 30
10 15
20 40

Sample Output 1

2 3 2 1

Employee 1 met employees 2,3; employee 2 met employees 1,3,4; employee 3 met employees 1,2; employee 4 met employee 2.

Sample Input 2

10
33553 130683
93150 198918
44559 198032
87304 140783
58113 161838
858 74380
39597 150815
2425 149780
8298 10367
37788 184869

Sample Output 2

8 7 8 7 8 7 8 9 2 8

Problem Statement

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

Process the given Q queries. There are two kinds of queries given as follows:

• 1 p c: Set the p-th character of S to the character c.
• 2 l r: Print how many times the most frequent letter occur, among the l-th through r-th characters of S.

Constraints

• 1\le N\le 2\times 10^5
• 1\le Q\le 2\times 10^5
• S is a string of length N, consisting of lowercase English letters.
• 1\le p\le N
• c is a lowercase English letter.
• 1\le l\le r\le N

Sample Input 1

6 4
abbabc
2 1 3
2 1 6
1 5 d
2 1 6

Sample Output 1

2
3
2

• The 1-st through 3-rd characters of S are abb. Among them, b occurs most frequently, namely 2 times. Thus, print 2 for the 1-st query.
• The 1-st through 6-th characters of S are abbabc. Among them, b occurs most frequently, namely 3 times. Thus, print 3 for the 2-nd query.
• For the 3-rd query, set the 5-th character of S to d, making S= abbadc.
• The 1-st through 6-th characters of S are abbadc. Among them, a and b occur most frequently, namely 2 times each. Thus, print 2 for the 4-th query.

Sample Input 2

8 4
nooutput
1 5 a
1 4 y
1 6 f
1 1 q

Sample Output 2

Sample Input 3

7 6
atcoder
2 1 7
1 1 r
2 1 7
1 2 r
2 1 7
1 4 r

Sample Output 3

1
2
3

Problem Statement

Takahashi and Aoki came to a conveyor belt sushi restaurant. Initially, each person's happiness is 0.

N dishes of sushi will approach them in order. Each dish is always taken by Takahashi or Aoki.
If Takahahsi takes the i-th dish, Takahashi's happiness increases by A_i; if Aoki takes it, Aoki's happiness increases by B_i. Here, the other person's happiness does not change.

They will distribute the N dishes in order so that the absolute difference of their happinesses does not exceed M at any moment. Find the maximum possible final happiness of Takahashi.

If they cannot distribute the N dishes in order so that the absolute difference of their happinesses does not exceed M at any moment, report that fact.

Constraints

• 1 \leq N \leq 10^5
• 1 \leq M \leq 100
• 1 \leq A_i,B_i \leq 100
• All input values are integers.

Sample Input 1

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

Sample Output 1

14

They can distribute the dishes as follows:

• Takahashi takes the 1-st dish. Takahashi's happiness is now 3, and Aoki's is 0.
• Takahashi takes the 2-nd dish. Takahashi's happiness is now 7, and Aoki's is 0.
• Aoki takes the 3-rd dish. Takahashi's happiness is now 7, and Aoki's is 9.
• Takahashi takes the 4-th dish. Takahashi's happiness is now 9, and Aoki's is 9.
• Takahashi takes the 5-th dish. Takahashi's happiness is now 14, and Aoki's is 9.

This yields the maximum value, because one cannot make the final happiness of Takahashi 15 or greater while keeping the absolute difference of their happinesses not greater than 7.

Sample Input 2

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

Sample Output 2

10

They can distribute the dishes as follows:

• Aoki takes the 1-st dish. Takahashi's happiness is now 0, and Aoki's is 1.
• Aoki takes the 2-nd dish. Takahashi's happiness is now 0, and Aoki's is 2.
• Takahashi takes the 3-rd dish. Takahashi's happiness is now 5, and Aoki's is 2.
• Aoki takes the 4-th dish. Takahashi's happiness is now 5, and Aoki's is 8.
• Takahashi takes the 5-th dish. Takahashi's happiness is now 10, and Aoki's is 8.

Sample Input 3

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

Sample Output 3

-1

Any distribution will make the absolute difference of the happinesses greater than 2 at some moment.

Sample Input 4

20 70
22 75
26 45
72 81
47 29
97 2
75 25
82 84
17 56
32 2
28 37
57 39
18 11
79 6
40 68
68 16
40 63
93 49
91 10
55 68
31 80

Sample Output 4

496

Problem Statement

AtCoder Republic has N towns numbered 1 through N, and M roads numbered 1 through M. Road i connects towns X_i and Y_i bidirectionally, and its length is C_i.

Takahashi is initially at town 1 with speed 1. When his speed is s, traveling along a length-C road takes \frac{C}{s} hours.

K towns, towns A_1,\ldots,A_K, have a gym. Every time he works out once for T hours in a gym, his speed increases by 1.
He can work out any number of times (possibly zero) in each gym.

Find the minimum hours required for him to reach town N.

Constraints

• 2 \leq N \leq 2 \times 10^5
• 0 \leq M \leq 2 \times 10^5
• 0 \leq K \leq N
• 1 \leq T \leq 10^6
• 1 \leq X_i,Y_i \leq N
• 1 \leq C_i \leq 10^6
• 1 \leq A_1 < \ldots < A_K \leq N
• It is reachable from town 1 to town N.
• All input values are integers.

Sample Input 1

3 2 1 15
1 2 100
2 3 100
2

Sample Output 1

163.333333333333343

The following moves allow him to travel from town 1 to 3 in \frac{490}{3}=163.333333\dots hours.

• Travel from town 1 to 2 via road 1, spending 100 hours.
• Work out in the gym at town 2 for 15 hours. Now his speed is 2.
• Work out in the gym at town 2 for 15 hours. Now his speed is 3.
• Travel from town 2 to 3 via road 2, spending \frac{100}{3} hours.

Sample Input 2

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

Sample Output 2

11.666666666666668

Sample Input 3

5 5 3 2
1 3 1
3 2 10
2 5 10
1 4 8
4 5 10
2 3 4

Sample Output 3

11.333333333333332

Problem Statement

You are given integers N and K, and a length-N string S consisting of lowercase English letters. When the \displaystyle \frac{N(N+1)}2 nonempty contiguous substrings of S are arranged in lexicographical order, find the K-th smallest string.

Constraints

• 1\le N\le 10^6
• \displaystyle 1\le K\le \frac{N(N+1)}2
• S is a string of length N consisting of lowercase English letters.

Sample Input 1

3 3
aba

Sample Output 1

ab

The nonempty substrings of S= aba are these six: a, ab, aba, b, ba, a. In lexicographical order, they are a, a, ab, aba, b, ba. Print the 3-rd smallest string ab.

Sample Input 2

5 8
wwwww

Sample Output 2

ww

Sample Input 3

8 28
chokudai

Sample Output 3

ok

Sample Input 4

22 30
atcoderbeginnercontest

Sample Output 4

beginner

Problem Statement

There is a grid with H horizontal rows and W vertical columns.

The cell in row i (counted from the top) and column j (from the left) has A_{i,j} written on it if A_{i,j}\neq -1, and is empty if A_{i,j}=-1.
Here, A_{i,j} is an integer between -1 and 9.

You will write an integer between 0 and 9, inclusive, to each empty cell so that:

• For any pair of cells that share a side, the numbers written on the two cells sum to D or less.

Find the maximum possible sum of the numbers newly written.

Constraints

• 1 \leq H,W \leq 15
• 0 \leq D \leq 18
• -1 \leq A_{i,j} \leq 9
• All input values are integers.
• There exists a conforming assignment of numbers.

Sample Input 1

2 3 10
5 -1 3
2 4 -1

Sample Output 1

11

By writing 5 to the cell in row 1 and column 2, and 6 to the cell in row 2 and column 3, the newly written numbers sum to 11, and any adjacent cells sum to 10 or less.

This is the maximum, because one cannot make the sum of newly written numbers 12 or greater.

Sample Input 2

2 1 18
-1
0

Sample Output 2

9

Note that we can only write integers between 0 and 9.

Sample Input 3

3 2 10
4 4
4 4
4 4

Sample Output 3

0

There may be no empty cell.

Sample Input 4

8 9 6
2 -1 3 -1 3 2 3 -1 3
-1 2 2 3 -1 3 -1 3 2
-1 3 -1 -1 3 2 3 2 -1
-1 -1 -1 2 2 3 2 -1 2
-1 3 1 -1 -1 2 3 2 2
-1 -1 -1 1 4 1 -1 -1 3
3 -1 -1 4 1 2 -1 -1 2
2 -1 -1 1 -1 -1 2 2 1

Sample Output 4

91