Problem Statement

Among the positive integers that consist of 0's and 2's when written in base 10, find the K-th smallest integer.

Constraints

• K is an integer between 1 and 10^{18} (inclusive).

Sample Input 1

3

Sample Output 1

22

The positive integers that consist of 0's and 2's when written in base 10 are 2,20,22,\dots in ascending order.
The (K=) 3-rd of them, which is 22, should be printed.

Sample Input 2

11

Sample Output 2

2022

Sample Input 3

923423423420220108

Sample Output 3

220022020000202020002022022000002020002222002200002022002200

Note that the exact value of the answer must be printed as an integer, even if it is big.

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

We have a tree with N vertices numbered 1, 2, \dots, N.
The i-th edge (1 \leq i \leq N - 1) connects Vertex u_i and Vertex v_i and has a weight w_i.

For different vertices u and v, let f(u, v) be the greatest weight of an edge contained in the shortest path from Vertex u to Vertex v.

Find \displaystyle \sum_{i = 1}^{N - 1} \sum_{j = i + 1}^N f(i, j).

Constraints

• 2 \leq N \leq 10^5
• 1 \leq u_i, v_i \leq N
• 1 \leq w_i \leq 10^7
• The given graph is a tree.
• All values in input are integers.

Sample Input 1

3
1 2 10
2 3 20

Sample Output 1

50

We have f(1, 2) = 10, f(2, 3) = 20, and f(1, 3) = 20, so we should print their sum, or 50.

Sample Input 2

5
1 2 1
2 3 2
4 2 5
3 5 14

Sample Output 2

76

Problem Statement

You are given N strings consisting of lowercase English letters. Let S_i be the i-th (i = 1, 2, \dots, N) of them.

For two strings x and y, \mathrm{LCP}(x, y) is defined to be the maximum integer n that satisfies all of the following conditions:

• The lengths of x and y are both at least n.
• For all integers i between 1 and n, inclusive, the i-th character of x and that of y are equal.

Find the following value for all i = 1, 2, \dots, N:

• \displaystyle \max_{i \neq j} \mathrm{LCP}(S_i, S_j)

Constraints

• 2 \leq N \leq 5 \times 10^5
• N is an integer.
• S_i is a string of length at least 1 consisting of lowercase English letters (i = 1, 2, \dots, N).
• The sum of lengths of S_i is at most 5 \times 10^5.

Sample Input 1

3
abc
abb
aac

Sample Output 1

2
2
1

\mathrm{LCP}(S_1, S_2) = 2, \mathrm{LCP}(S_1, S_3) = 1, and \mathrm{LCP}(S_2, S_3) = 1.

Sample Input 2

11
abracadabra
bracadabra
racadabra
acadabra
cadabra
adabra
dabra
abra
bra
ra
a

Sample Output 2

4
3
2
1
0
1
0
4
3
2
1

Problem Statement

Find the maximum side length of a regular triangle that can be drawn within a rectangle whose side lengths are A and B.

Constraints

• 1 \leq A,B \leq 1000
• A and B are integers.

Sample Input 1

1 1

Sample Output 1

1.03527618041008295791

The following figure shows an optimal drawing, with the side length of \sqrt{6} - \sqrt{2}.

Note that the sample output does not strictly match \sqrt{6}- \sqrt{2}, but the error is within 10^{-9}, so it is considered correct.