Problem Statement

There are N people standing in a line: person 1, person 2, \ldots, person N.

You are given the arrangement of the people as a sequence A=(A _ 1,A _ 2,\ldots,A _ N) of length N.

A _ i\ (1\leq i\leq N) represents the following information:

• if A _ i=-1, person i is at the front of the line;
• if A _ i\neq -1, person i is right behind person A _ i.

Print the people's numbers in the line from front to back.

Constraints

• 1\leq N\leq3\times10 ^ 5
• A _ i=-1 or 1\leq A _ i\leq N\ (1\leq i\leq N)
• There is exactly one way to arrange the N people consistent with the information given.
• All input values are integers.

Sample Input 1

6
4 1 -1 5 3 2

Sample Output 1

3 5 4 1 2 6

If person 3, person 5, person 4, person 1, person 2, and person 6 stand in line in this order from front to back, the arrangement matches the given information.

Indeed, it can be seen that:

• person 1 is standing right behind person 4,
• person 2 is standing right behind person 1,
• person 3 is at the front of the line,
• person 4 is standing right behind person 5,
• person 5 is standing right behind person 3, and
• person 6 is standing right behind person 2.

Thus, print 3, 5, 4, 1, 2, and 6 in this order, separated by spaces.

Sample Input 2

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

Sample Output 2

1 2 3 4 5 6 7 8 9 10

Sample Input 3

30
3 25 20 6 18 12 26 1 29 -1 21 17 23 9 8 30 10 15 22 27 4 13 5 11 16 24 28 2 19 7

Sample Output 3

10 17 12 6 4 21 11 24 26 7 30 16 25 2 28 27 20 3 1 8 15 18 5 23 13 22 19 29 9 14

Problem Statement

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

You will perform an operation Q times on the string S. The i-th operation (1\leq i\leq Q) is represented by a pair of characters (c _ i,d _ i), which corresponds to the following operation:

• Replace all occurrences of the character c _ i in S with the character d _ i.

Print the string S after all operations are completed.

Constraints

• 1\leq N\leq2\times10^5
• S is a string of length N consisting of lowercase English letters.
• 1\leq Q\leq2\times10^5
• c _ i and d _ i are lowercase English letters (1\leq i\leq Q).
• N and Q are integers.

Sample Input 1

7
atcoder
4
r a
t e
d v
a r

Sample Output 1

recover

S changes as follows: atcoder → atcodea → aecodea → aecovea → recover. For example, in the fourth operation, all occurrences of a in S={}aecovea (the first and seventh characters) are replaced with r, resulting in S={}recover.

After all operations are completed, S={}recover, so print recover.

Sample Input 2

3
abc
4
a a
s k
n n
z b

Sample Output 2

abc

There may be operations where c _ i=d _ i or S does not contain c _ i.

Sample Input 3

34
supercalifragilisticexpialidocious
20
g c
l g
g m
c m
r o
s e
a a
o f
f s
e t
t l
d v
p k
v h
x i
h n
n j
i r
s i
u a

Sample Output 3

laklimamriiamrmrllrmlrkramrjimrial

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

There are N types of products, each having 10^{100} units in stock.

You can buy any non-negative number of units of each product. To buy k units of the i-th product, it costs k^2 P_i yen.

If your total purchase cost is at most M yen, what is the maximum number of units you can buy in total?

Constraints

• 1 \leq N \leq 2 \times 10^{5}
• 1 \leq M \leq 10^{18}
• 1 \leq P_i \leq 2 \times 10^{9}
• All input values are integers.

Sample Input 1

3 9
4 1 9

Sample Output 1

3

If you buy one unit of the 1st product and two units of the 2nd product, the total purchase cost is 1^2 \times 4 + 2^2 \times 1 = 8. It is impossible to buy four or more units in total with a total cost of at most 9 yen, so the answer is 3.

Sample Input 2

10 1000
2 15 6 5 12 1 7 9 17 2

Sample Output 2

53

Problem Statement

You are given N integers A_1, A_2, \dots, A_N.
Find the number of triples of integers (i, j, k) that satisfy the following conditions:

• 1 \le i, j, k \le N
• A_i \times A_j = A_k

Constraints

• 1 \le N \le 1000
• \color{red}{1 \le A_i < 10^{1000}}

Sample Input 1

5
2
3
6
12
24

Sample Output 1

6

The following six triples (i, j, k) satisfy the conditions in the problem statement:

• (1, 2, 3)
• (1, 3, 4)
• (1, 4, 5)
• (2, 1, 3)
• (3, 1, 4)
• (4, 1, 5)

Sample Input 2

11
1
2
3
4
5
6
123456789123456789
123456789123456789
987654321987654321
987654321987654321
121932631356500531347203169112635269

Sample Output 2

40

Note that the values of each integer A_i can be huge.

Sample Input 3

9
4
4
4
2
2
2
1
1
1

Sample Output 3

162

Note that there may be duplicates among the values of A_i.