Problem Statement

Takahashi is investigating which buildings on a university campus can be reached by the signal from a Wi-Fi router installed on campus.

There are N buildings on the campus, and the i-th building (1 \leq i \leq N) is located at coordinates (X_i, Y_i). Multiple buildings may exist at the same coordinates, but each is counted as a separate building.

The Wi-Fi router is installed on the rooftop of the administration building located at coordinates (0, 0). The administration building is not included in the N buildings being investigated.

The Wi-Fi signal reaches buildings whose Euclidean distance from the router is at most D. That is, the Wi-Fi signal reaches the i-th building when

\sqrt{X_i^2 + Y_i^2} \leq D

is satisfied, or equivalently when

X_i^2 + Y_i^2 \leq D^2

is satisfied.

Find the number of buildings that the Wi-Fi signal does not reach.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq D \leq 10^6
• -10^6 \leq X_i \leq 10^6
• -10^6 \leq Y_i \leq 10^6
• All inputs are integers

Sample Input 1

5 10
3 4
8 6
12 5
-5 0
7 -7

Sample Output 1

1

Sample Input 2

8 100
50 50
-30 40
80 60
0 100
100 1
-70 -70
25 -25
0 -150

Sample Output 2

2

Sample Input 3

12 1000
100 200
-500 500
700 700
0 1000
1000 0
-800 -600
300 -400
999 1
-1 999
600 800
-707 -708
450 -900

Sample Output 3

2

Problem Statement

Takahashi works at a lottery ticket booth. In this lottery, a total of N tickets are sold, each printed with a unique number from 1 to N. The winning condition is determined by the digit sum of the ticket number. Here, the digit sum of a positive integer is the sum of its digits in its decimal representation. For example, the digit sum of 123 is 1 + 2 + 3 = 6.

Specifically, a ticket is a "winning ticket" if the digit sum of its ticket number modulo K is equal to R.

Takahashi became interested in cases where three consecutive ticket numbers x-1, x, x+1 are all winning tickets.

You are given a positive integer N, a positive integer K, and a non-negative integer R. Let \mathrm{digitsum}(n) denote the digit sum of an integer n. Find the number of integers x satisfying 2 \leq x \leq N - 1 such that all of the following three conditions are met, modulo 10^9 + 7:

(\mathrm{digitsum}(x-1)) \bmod K = R, \quad (\mathrm{digitsum}(x)) \bmod K = R, \quad (\mathrm{digitsum}(x+1)) \bmod K = R

Constraints

• N is an integer of at least 3
• N is given as a string in decimal representation, without leading zeros
• The length of the decimal representation of N is at most 5 \times 10^6
• 1 \leq K \leq 100
• 0 \leq R \leq K - 1

Sample Input 1

25 3 1

Sample Output 1

0

Sample Input 2

50 7 0

Sample Output 2

0

Sample Input 3

123456789 9 6

Sample Output 3

0

Sample Input 4

100000000000000000000000000000000000000000000000000 97 42

Sample Output 4

0

Sample Input 5

3 1 0

Sample Output 5

1

Problem Statement

Takahashi is trying to travel from town 1 to town N.

There are N towns and M roads, and the i-th road bidirectionally connects town U_i and town V_i.

Currently, some roads are closed due to construction. Specifically, when S_i = 1, the i-th road is passable, and when S_i = 0, it is closed and cannot be used.

Takahashi travels from town 1 to town N using only passable roads. During the trip, he may pass through the same town or the same road multiple times. Find the minimum number of roads traversed (if the same road is used multiple times, each traversal is counted separately).

However, if it is impossible to reach town N using only passable roads regardless of the route taken, output -1.

Constraints

• 2 \leq N \leq 2 \times 10^5
• 1 \leq M < 2 \times 10^5
• 1 \leq U_i, V_i \leq N
• U_i \neq V_i
• There may be multiple roads for the same pair (U_i, V_i) (i.e., multiple edges are possible; the value of S_i is determined independently for each road)
• S_i \in \{0, 1\}
• All input values are integers

Sample Input 1

4 5
1 2 1
2 4 1
1 3 0
3 4 1
2 3 1

Sample Output 1

2

Sample Input 2

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

Sample Output 2

-1

Sample Input 3

8 12
1 2 1
1 3 0
2 4 1
3 4 1
4 5 0
4 6 1
6 8 1
5 8 1
2 3 1
2 5 1
1 2 0
7 8 1

Sample Output 3

3

Sample Input 4

12 20
1 2 1
2 3 1
3 12 0
1 4 1
4 5 1
5 6 1
6 12 1
2 5 0
3 6 1
1 7 0
7 8 1
8 9 1
9 12 1
4 8 1
5 9 0
2 10 1
10 11 1
11 12 1
6 10 0
3 4 1

Sample Output 4

4

Sample Input 5

2 1
1 2 1

Sample Output 5

1

Problem Statement

Takahashi has a bead sequence represented by a string of length N consisting of two types of characters: A and B. The bead sequence is a linear sequence where the front and back are distinguished. The initial state of the bead sequence is represented by the string S.

Takahashi can perform the following 3 types of operations on the bead sequence, in any order, zero or more times, for any total number of times. Each operation is applied to the current state of the bead sequence.

• Rotate left: Perform a cyclic left shift on the bead sequence. That is, remove the first character and append it to the end.
• Rotate right: Perform a cyclic right shift on the bead sequence. That is, remove the last character and prepend it to the front.
• Pattern duplication: Choose a positive divisor d of N (d < N). The value of d can be freely chosen for each operation. Let P be the first d characters of the current bead sequence, and replace the entire bead sequence with the string obtained by repeating P exactly N / d times concatenated together.

Takahashi wants to make the bead sequence match the target string T.

Find the minimum number of operations required to make S match T. If S already matches T, output 0. If it is impossible to make S match T no matter what operations are performed, output -1.

Constraints

• 1 \leq N \leq 25
• S is a string of length N consisting of A and B
• T is a string of length N consisting of A and B

Sample Input 1

6
ABBAAA
ABABAB

Sample Output 1

1

Sample Input 2

5
AAAAB
AABAB

Sample Output 2

-1

Sample Input 3

12
BAABABBAAAAA
ABBAABBAABBA

Sample Output 3

3

Sample Input 4

24
BABAAABBABBBABAAAABBABBA
AABBABAABBABAABBABAABBAB

Sample Output 4

5

Sample Input 5

1
A
A

Sample Output 5

0

Problem Statement

There is a communication network consisting of N base stations. The base stations are numbered from 1 to N. These base stations are connected by N - 1 communication lines, and any base station can communicate with any other base station by traversing the lines (that is, they form a tree structure). The i-th line (1 \leq i \leq N-1) bidirectionally connects base station A_i and base station B_i. Also, base station j (1 \leq j \leq N) stores data of volume V_j.

In this network, Takahashi (the attacker) and Aoki (the administrator) play a game according to the following procedure:

1. Aoki's Action: Aoki chooses to disconnect one of the N - 1 lines, or decides not to disconnect any lines. Disconnected lines become unusable. Aoki can disconnect at most one line.
2. Takahashi's Action: Knowing exactly which line Aoki disconnected (or that he did not disconnect any), Takahashi chooses one base station from the N base stations as the target of his intrusion. Even if the network is disconnected, Takahashi can choose any base station as the target.
3. Result: Takahashi steals data from all base stations that can be reached from the target base station within a distance of D or less, using only the usable (not disconnected) lines. He always steals data from the target base station itself.

Here, the distance between two base stations is defined as the minimum number of lines traversed to reach one from the other using only usable lines. If they cannot reach each other using only usable lines, the distance is considered to be \infty. In particular, the distance from the target base station to itself is 0.

Takahashi acts to maximize the total volume of data stolen, and Aoki acts to minimize it. Find the total volume of data Takahashi can steal when both players play optimally.

Constraints

• 2 \leq N \leq 3000
• 1 \leq D \leq N - 1
• 1 \leq V_i \leq 10^9 (1 \leq i \leq N)
• 1 \leq A_i, B_i \leq N (1 \leq i \leq N - 1)
• The graph given in the input is a tree.
• All input values are integers.

Sample Input 1

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

Sample Output 1

15

Sample Input 2

5 2
1 100 1 100 1
1 2
1 3
3 4
3 5

Sample Output 2

102

Sample Input 3

12 2
8 6 15 3 10 7 20 1 9 4 12 5
1 2
1 3
2 4
2 5
3 6
3 7
5 8
5 9
7 10
7 11
11 12

Sample Output 3

52

Sample Input 4

25 4
17 23 5 100 8 42 11 6 29 31 7 13 19 2 53 47 3 37 41 59 61 67 71 73 79
1 2
1 3
2 4
2 5
3 6
3 7
4 8
4 9
5 10
5 11
6 12
6 13
7 14
7 15
8 16
9 17
10 18
11 19
12 20
13 21
14 22
15 23
20 24
20 25

Sample Output 4

555

Sample Input 5

2 1
1000000000 1
1 2

Sample Output 5

1000000000