Problem Statement

You are given a string S of length N consisting of three kinds of characters: ., |, and *. S contains exactly two | and exactly one *.

Determine whether the * is between the two |, and if so, print in; otherwise, print out.

More formally, determine whether one of the characters before the * is | and one of the characters after the * is |.

Constraints

• 3\leq N\leq 100
• N is an integer.
• S is a string of length N consisting of ., |, and *.
• S contains exactly two |.
• S contains exactly one *.

Sample Input 1

10
.|..*...|.

Sample Output 1

in

Between the two |, we have |..*...|, which contains *, so you should print in.

Sample Input 2

10
.|..|.*...

Sample Output 2

out

Between the two |, we have |..|, which does not contain *, so you should print out.

Sample Input 3

3
|*|

Sample Output 3

in

Problem Statement

You are given a string S of length exactly 9 consisting of digits. One but all digits from 0 to 9 appear exactly once in S.

Print the only digit missing in S.

Constraints

• S is a string of length 9 consisting of digits.
• All characters in S are distinct.

Sample Input 1

023456789

Sample Output 1

1

The string 023456789 only lacks 1. Thus, 1 should be printed.

Sample Input 2

459230781

Sample Output 2

6

The string 459230781 only lacks 6. Thus, 6 should be printed.

Note that the digits in the string may not appear in increasing order.

Problem Statement

You are given an integer N between -10^{18} and 10^{18} (inclusive).

Find an integer x between 0 and 998244353 - 1 (inclusive) that satisfies the following condition. It can be proved that such an integer is unique.

• N-x is a multiple of 998244353.

Constraints

• N is an integer between -10^{18} and 10^{18} (inclusive).

Sample Input 1

998244354

Sample Output 1

1

998244354-1 = 998244353 is a multiple of 998244353, so the condition is satisfied.

Sample Input 2

-9982443534

Sample Output 2

998244349

-9982443534-998244349= -10980687883 is a multiple of 998244353, so the condition is satisfied.

Problem Statement

You are given N strings S_1,S_2,\ldots,S_N consisting of lowercase English letters.
Determine if there are distinct integers i and j between 1 and N, inclusive, such that the concatenation of S_i and S_j in this order is a palindrome.

A string T of length M is a palindrome if and only if the i-th character and the (M+1-i)-th character of T are the same for every 1\leq i\leq M.

Constraints

• 2\leq N\leq 100
• 1\leq \lvert S_i\rvert \leq 50
• N is an integer.
• S_i is a string consisting of lowercase English letters.
• All S_i are distinct.

Sample Input 1

5
ab
ccef
da
a
fe

Sample Output 1

Yes

If we take (i,j)=(1,4), the concatenation of S_1=ab and S_4=a in this order is aba, which is a palindrome, satisfying the condition.
Thus, print Yes.

Here, we can also take (i,j)=(5,2), for which the concatenation of S_5=fe and S_2=ccef in this order is feccef, satisfying the condition.

Sample Input 2

3
a
b
aba

Sample Output 2

No

No two distinct strings among S_1, S_2, and S_3 form a palindrome when concatenated. Thus, print No.
Note that the i and j in the statement must be distinct.

Sample Input 3

2
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa

Sample Output 3

Yes

Problem Statement

A region has N towns numbered 1 to N, and M roads numbered 1 to M.

The i-th road connects town A_i and town B_i bidirectionally with length C_i.

Find the maximum possible total length of the roads you traverse when starting from a town of your choice and getting to another town without passing through the same town more than once.

Constraints

• 2 \leq N \leq 10
• 1 \leq M \leq \frac{N(N-1)}{2}
• 1 \leq A_i < B_i \leq N
• The pairs (A_i,B_i) are distinct.
• 1\leq C_i \leq 10^8
• All input values are integers.

Sample Input 1

4 4
1 2 1
2 3 10
1 3 100
1 4 1000

Sample Output 1

1110

If you travel as 4\to 1\to 3\to 2, the total length of the roads you traverse is 1110.

Sample Input 2

10 1
5 9 1

Sample Output 2

1

There may be a town that is not connected to a road.

Sample Input 3

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

Sample Output 3

20

Problem Statement

A repunit is an integer whose digits are all 1 in decimal representation. The repunits in ascending order are 1, 11, 111, \ldots.

Find the N-th smallest integer that can be expressed as the sum of exactly three repunits.

Constraints

• N is an integer between 1 and 333, inclusive.

Sample Input 1

5

Sample Output 1

113

The integers that can be expressed as the sum of exactly three repunits are 3, 13, 23, 33, 113, \ldots in ascending order. For example, 113 can be expressed as 113 = 1 + 1 + 111.

Note that the three repunits do not have to be distinct.

Sample Input 2

19

Sample Output 2

2333

Sample Input 3

333

Sample Output 3

112222222233

Problem Statement

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

Find the number of triplets of integers (i, j, k) satisfying all of the conditions below.

• 1 \leq i, j, k \leq N
• \frac{A_i}{A_j} = A_k

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq A_i \leq 2 \times 10^5 \, (1 \leq i \leq N)
• All values in input are integers.

Sample Input 1

3
6 2 3

Sample Output 1

2

(i, j, k) = (1, 2, 3), (1, 3, 2) satisfy the conditions.

Sample Input 2

1
2

Sample Output 2

0

Sample Input 3

10
1 3 2 4 6 8 2 2 3 7

Sample Output 3

62

Problem Statement

You are given a simple directed graph with N vertices numbered 1 to N and M edges numbered 1 to M. Edge i is a directed edge from vertex u_i to vertex v_i.

You may perform the following operation zero or more times.

• Choose distinct vertices x and y such that there is no directed edge from vertex x to vertex y, and add a directed edge from vertex x to vertex y.

Find the minimum number of times you need to perform the operation to make the graph satisfy the following condition.

• For every triple of distinct vertices a, b, and c, if there are directed edges from vertex a to vertex b and from vertex b to vertex c, there is also a directed edge from vertex a to vertex c.

Constraints

• 3 \leq N \leq 2000
• 0 \leq M \leq 2000
• 1 \leq u_i ,v_i \leq N
• u_i \neq v_i
• (u_i,v_i) \neq (u_j,v_j) if i \neq j.
• All values in the input are integers.

Sample Input 1

4 3
2 4
3 1
4 3

Sample Output 1

3

Initially, the condition is not satisfied because, for instance, for vertices 2, 4, and 3, there are directed edges from vertex 2 to vertex 4 and from vertex 4 to vertex 3, but not from vertex 2 to vertex 3.

You can make the graph satisfy the condition by adding the following three directed edges:

• one from vertex 2 to vertex 3,
• one from vertex 2 to vertex 1, and
• one from vertex 4 to vertex 1.

On the other hand, the condition cannot be satisfied by adding two or fewer edges, so the answer is 3.

Sample Input 2

292 0

Sample Output 2

0

Sample Input 3

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

Sample Output 3

12

Problem Statement

We have a grid with 10^9 rows and 10^9 columns. Let (i,j) denote the square at the i-th row from the top and j-th column from the left.

For i=1,2,\ldots,N, a positive integer x_i is written on (r_i,c_i). On the other 10^{18}-N squares, 0 is written.

You choose a square (R,C) and compute the sum S of the integers written on the 2 \times 10^9 - 1 squares that share a row or column with (R,C).

Find the maximum possible value of S.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq r_i,c_i,x_i \leq 10^9
• (r_i,c_i) \neq (r_j,c_j) if i \neq j.
• All values in the input are integers.

Sample Input 1

4
1 1 2
1 2 9
2 1 8
3 2 3

Sample Output 1

20

If you choose (2,2) as (R,C), then S will be 20, which is the maximum possible value.

Sample Input 2

1
1 1000000000 1

Sample Output 2

1

Sample Input 3

15
158260522 877914575 602436426
24979445 861648772 623690081
433933447 476190629 262703497
211047202 971407775 628894325
731963982 822804784 450968417
430302156 982631932 161735902
880895728 923078537 707723857
189330739 910286918 802329211
404539679 303238506 317063340
492686568 773361868 125660016
650287940 839296263 462224593
492601449 384836991 191890310
576823355 782177068 404011431
818008580 954291757 160449218
155374934 840594328 164163676

Sample Output 3

1510053068