Problem Statement

A Supermarket Takahashi sells an X-gram beef pack for Y yen.
Another Supermarket Snuke has decided to sell a beef pack at a lower price per gram.
In Snuke, one beef pack weighs Z grams. What is the greatest possible price (a non-negative integer) for Snuke's beef pack such that it is strictly cheaper than Takahashi's beef pack per gram?

Constraints

• All values in input are integers.
• 1 ≤ X, Y, Z ≤ 10^3

Sample Input 1

100 200 100

Sample Output 1

199

Both stores sell 100-gram packs, so Snuke can just make it one yen cheaper than that in Takahashi.

Sample Input 2

103 971 593

Sample Output 2

5590

Takahashi sells beef for \frac{971}{103} = 9.4271\dots yen per gram. Snuke can sell 593 grams of beef for 5590 yen to make it \frac{5590}{593} = 9.4266\dots yen per gram.

Sample Input 3

1000 1 1

Sample Output 3

0

The price is allowed to be 0 yen.

Problem Statement

We have two strictly increasing integer sequences A = (A_1, A_2, \dots, A_N) and B = (B_1, B_2, \dots, B_M).
Find all integers that appear in exactly one of A and B and print them in ascending order.

Constraints

• All values in input are integers.
• 1 \leq N, M \leq 10^3
• 1 \leq A_1 < A_2 < \dots < A_N \leq 10^3
• 1 \leq B_1 < B_2 < \dots < B_M \leq 10^3

Sample Input 1

2 2
1 2
1 3

Sample Output 1

2 3

1 is contained in both A and B;
2 is contained in only A;
3 is contained in only B.
Thus, we should print 2 and 3.

Sample Input 2

4 4
1 2 3 4
1 2 3 4

Sample Output 2

You can print an empty line or nothing.

Problem Statement

Given are integers A and B. Find the maximum possible value of \gcd(x, y) when we choose integers x and y so that A ≤ x < y ≤ B.
Here, \gcd(x, y) denotes the greatest common divisor of x and y.

Constraints

• A and B are integers.
• 1 ≤ A < B ≤ 2 \times 10^5

Sample Input 1

2 4

Sample Output 1

2

We have three ways to choose (x, y) such that A ≤ x < y ≤ B: (2,3), (2,4), (3,4), where the greatest common divisors are 1, 2, 1, respectively, so the maximum possible value is 2.

Sample Input 2

199999 200000

Sample Output 2

1

We have \gcd(199999, 200000) = 1.

Sample Input 3

101 139

Sample Output 3

34

Problem Statement

You are given a prime number P not less than 2, which you don't like.

Let's call an array of integers A_1, A_2, \dots, A_N very good if it satisfies the following condition:

• there is no i with 1 \le i \le N and A_1 + A_2 + \dots + A_i \equiv 0 \bmod P.

Consider all (P-1)^N arrays of length N with elements from 1 to P-1. How many of them are very good?

As this number can be very big, output it modulo (10^9 + 7).

Constraints

• N and P are integers.
• 1 ≤ N ≤ 10^9
• 2 ≤ P ≤ 10^9

Sample Input 1

3 3

Sample Output 1

2

Two arrays, (1, 1, 2) and (2, 2, 1), satisfy the condition.

Sample Input 2

3 2

Sample Output 2

0

Sample Input 3

45108 2571593

Sample Output 3

224219544

Problem Statement

As a token of his gratitude, Takahashi has decided to give Snuke a level-K palindrome. A level-L palindrome, where L is a non-negative integer, is defined as follows:

• Let \mathrm{rev}(s) denote the reversal of a string s.
• A string s is said to be a palindrome when s = \mathrm{rev}(s).
• The empty string and a string that is not a palindrome are level-0 palindromes.
• For any non-empty level-(L-1) palindrome t, the concatenation of t, \mathrm{rev}(t) in this order is a level-L palindrome.
• For any level-(L-1) palindrome t and any character c, the concatenation of t, c, \mathrm{rev}(t) in this order is a level-L palindrome.

Now, Takahashi has a string S. Determine whether it is possible to make S an exactly level-K palindrome by doing the following action zero or more times: choose a character in S and change it to another lowercase English letter. If it is possible, find the minimum number of changes needed to make S a level-K palindrome.

Constraints

• K is an integer.
• 0 ≤ K ≤ 5 \times 10^5
• S consists of lowercase English letters.
• 1 ≤ |S| ≤ 5 \times 10^5

Sample Input 1

4
aabaaaabaa

Sample Output 1

0

We can find the level of aabaaaabaa as follows:

• the empty string is a level-0 palindrome;
• a is a concatenation of (empty string), a, (empty string) in this order, so it is a level-1 palindrome;
• aa is a concatenation of a, a in this order, so it is a level-2 palindrome;
• aabaa is a concatenation of aa, b, aa in this order, so it is a level-3 palindrome;
• aabaaaabaa is a concatenation of aabaa, aabaa in this order, so it is a level-4 palindrome.

Thus, aabaaaabaa is already a level-4 palindrome and needs no changes.

Sample Input 2

2
aabaaaabaa

Sample Output 2

4

We can, for example, change aabaaaabaa to acbcaacbca to get a level-2 palindrome.

Note that aabaaaabaa is not a level-2 palindrome.

Sample Input 3

3
aabaaaabaa

Sample Output 3

impossible

Sample Input 4

5
aabaaaabaa

Sample Output 4

impossible

Sample Input 5

2
acaabcbababaaac

Sample Output 5

6

Problem Statement

We have a sequence a of length N and a sequence b of length M. Initially, every element in a and b is 0.
You are asked to process Q queries. In the i-th query, given three integers T_i, X_i, and Y_i, do the following:

• if T_i = 1: replace a_{X_i} with Y_i;
• if T_i = 2: replace b_{X_i} with Y_i.

Then, after processing each query, print the value \displaystyle \sum_{i = 1}^N \sum_{j = 1}^M \max(a_i, b_j).

Constraints

• 1 \le N \le 2 \times 10^5
• 1 \le M \le 2 \times 10^5
• 1 \le Q \le 2 \times 10^5
• T_i is 1 or 2.
• If T_i = 1, 1 \le X_i \le N.
• If T_i = 2, 1 \le X_i \le M.
• 1 \le Y_i \le 10^8
• All values in input are integers.

Sample Input 1

2 2 4
1 1 10
2 1 20
2 2 5
1 1 30

Sample Output 1

20
50
55
85

If we write \max(a_i, b_j) at the i-th row and j-th column in a grid, the four queries will change it as follows:

Sample Input 2

3 3 5
1 3 10
2 1 7
1 3 5
2 2 10
2 1 1

Sample Output 2

30
44
31
56
42

Sample Input 3

200000 200000 4
2 112219 100000000
1 73821 100000000
2 26402 100000000
1 73821 100000000

Sample Output 3

20000000000000
39999900000000
59999800000000
59999800000000

The integers to be printed may not fit into a 32-bit integer type.

Problem Statement

We have a graph with N vertices numbered 1, 2, \dots, N. Initially, it has no edges.
Now, let us add some number of undirected edges to G so that the following condition holds for any i, j\,(i ≠ j) after addition.

• If A_{i, j} = 1, there is an edge directly connecting Vertex i and Vertex j;
• if A_{i, j} = 0, there is no edge directly connecting Vertex i and Vertex j;
• if A_{i, j} = -1, either is fine.

Among the graphs that can be G after addition, how many are trees?
Since the count can be enormous, find it modulo (10^9 + 7).

Constraints

• All values in input are integers.
• 2 ≤ N ≤ 300
• -1 ≤ A_{i, j} = A_{j, i} ≤ 1
• A_{i, i} = 0

Sample Input 1

4
0 1 -1 0
1 0 -1 -1
-1 -1 0 0
0 -1 0 0

Sample Output 1

2

We need an edge between Vertex 1 and Vertex 2, and we must not add an edge between Vertex 1 and Vertex 4 or between Vertex 3 and Vertex 4.

Thus, we have the following two valid graphs:

Sample Input 2

3
0 1 1
1 0 1
1 1 0

Sample Output 2

0

Sample Input 3

3
0 0 0
0 0 0
0 0 0

Sample Output 3

0

Sample Input 4

11
0 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
-1 0 -1 -1 -1 -1 -1 -1 -1 -1 -1
-1 -1 0 -1 -1 -1 -1 -1 -1 -1 -1
-1 -1 -1 0 -1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 0 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 0 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 0 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1 0 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1 -1 0 -1 -1
-1 -1 -1 -1 -1 -1 -1 -1 -1 0 -1
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 0

Sample Output 4

357947677

When we distinguish the vertices, there are 11^9 trees with 11 vertices.

Problem Statement

In the Republic of AtCoder, there are N cities called City 1 through City N and N canals called Canal 1 through Canal N.
Canal i connects City i and City A_i bidirectionally, and you have to pay the toll of C_i yen to go through it, but after paying the toll once, you can use it any number of times in any direction.
It is guaranteed that you can reach from any city to any city using some canals.

You are asked to deliver M cargoes in this country. The i-th cargo should be delivered from City X_i to City Y_i.
There is no way other than using the canals to deliver the cargoes, but you yourself can travel between the cities freely without using the canals.

Find the minimum total toll you have to pay to deliver all M cargoes.

Constraints

• 3 \le N \le 2 \times 10^5
• 1 \le M \le 2 \times 10^5
• 1 \le A_i \le N
• A_i \neq i
• 1 \le C_i \le 10^9
• It is possible to reach from any city to any city by using some canals.
• 1 \le X_i \le N
• 1 \le Y_i \le N
• X_i \neq Y_i
• All values in input are integers.

Sample Input 1

4 2
3 3
1 7
2 5
1 2
4 3
2 1

Sample Output 1

10

The figure below shows the cities and canals in this country, where numbers along the lines representing canals represent the tolls:

You can deliver the cargoes as follows to make the total toll 10 yen:

• The 1-st cargo: use Canal 1, 4 to deliver it on the route: City 4, 1, 3.
• The 2-nd cargo: use Canal 3, 1 to deliver it on this route: City 2, 3, 1.

Sample Input 2

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

Sample Output 2

13

Multiple canals may connect the same pair of cities.

Sample Input 3

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

Sample Output 3

26