Problem Statement

Your refrigerator has N kinds of ingredients. Let us call them ingredient 1, \dots, ingredient N. You have Q_i grams of ingredient i.

You can make two types of dishes. To make one serving of dish A, you need A_i grams of each ingredient i (1 \leq i \leq N). To make one serving of dish B, you need B_i grams of each ingredient i. You can only make an integer number of servings of each type of dish.

Using only the ingredients in the refrigerator, what is the maximum total number of servings of dishes you can make?

Constraints

• 1 \leq N \leq 10
• 1 \leq Q_i \leq 10^6
• 0 \leq A_i \leq 10^6
• There is an i such that A_i \geq 1.
• 0 \leq B_i \leq 10^6
• There is an i such that B_i \geq 1.
• All input values are integers.

Sample Input 1

2
800 300
100 100
200 10

Sample Output 1

5

This refrigerator has 800 grams of ingredient 1 and 300 grams of ingredient 2.

You can make one serving of dish A with 100 grams of ingredient 1 and 100 grams of ingredient 2, and one serving of dish B with 200 grams of ingredient 1 and 10 grams of ingredient 2.

To make two servings of dish A and three servings of dish B, you need 100 \times 2 + 200 \times 3 = 800 grams of ingredient 1, and 100 \times 2 + 10 \times 3 = 230 grams of ingredient 2, neither of which exceeds the amount available in the refrigerator. In this way, you can make a total of five servings of dishes, but there is no way to make six, so the answer is 5.

Sample Input 2

2
800 300
100 0
0 10

Sample Output 2

38

You can make 8 servings of dish A with 800 grams of ingredient 1, and 30 servings of dish B with 300 grams of ingredient 2, for a total of 38 servings.

Sample Input 3

2
800 300
801 300
800 301

Sample Output 3

0

You cannot make any dishes.

Sample Input 4

10
1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000
0 1 2 3 4 5 6 7 8 9
9 8 7 6 5 4 3 2 1 0

Sample Output 4

222222

Problem Statement

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

Find the maximum value of \displaystyle \sum_{i=1}^{M} i \times B_i for a contiguous subarray B=(B_1,B_2,\dots,B_M) of A of length M.

Notes

A contiguous subarray of a number sequence is a sequence that is obtained by removing 0 or more initial terms and 0 or more final terms from the original number sequence.

For example, (2, 3) and (1, 2, 3) are contiguous subarrays of (1, 2, 3, 4), but (1, 3) and (3,2,1) are not contiguous subarrays of (1, 2, 3, 4).

Constraints

• 1 \le M \le N \le 2 \times 10^5
• - 2 \times 10^5 \le A_i \le 2 \times 10^5
• All values in input are integers.

Sample Input 1

4 2
5 4 -1 8

Sample Output 1

15

When B=(A_3,A_4), we have \displaystyle \sum_{i=1}^{M} i \times B_i = 1 \times (-1) + 2 \times 8 = 15. Since it is impossible to achieve 16 or a larger value, the solution is 15.

Note that you are not allowed to choose, for instance, B=(A_1,A_4).

Sample Input 2

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

Sample Output 2

31

Problem Statement

You are given a sequence of length N: A=(A_1,\ldots,A_N).

Answer Q queries given in the following format.

• You are given integers L, R, and X. Find the number of elements among A_L, \ldots, A_R whose values are equal to X.

Constraints

• 1 \leq N \leq 2\times 10^5
• 1 \leq A_i \leq N
• 1 \leq Q \leq 2\times 10^5
• 1\le L \leq R \leq N, 1 \leq X \leq N, for each query.
• All values in input are integers.

Sample Input 1

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

Sample Output 1

2
0
0
1

In the first query, two of (A_1,A_2,A_3,A_4,A_5) =(3,1,4,1,5) have values equal to 1.

In the second query, zero of (A_2,A_3,A_4) =(1,4,1) have values equal to 3.

Problem Statement

You are given a simple undirected graph with N vertices numbered 1 to N and M edges numbered 1 to M. Edge i connects vertex u_i and vertex v_i. The degree of each vertex is at most 10.
Let K be the number of simple paths (paths without repeated vertices) starting from vertex 1. Print \min(K, 10^6).

Constraints

• 1 \leq N \leq 2 \times 10^5
• 0 \leq M \leq \min \left(2 \times 10^5, \frac{N(N-1)}{2}\right)
• 1 \leq u_i, v_i \leq N
• The given graph is simple.
• The degree of each vertex in the given graph is at most 10.
• All values in the input are integers.

Sample Input 1

4 2
1 2
2 3

Sample Output 1

3

We have the following three paths that count. (Note that a path of length 0 also counts.)

• Vertex 1;
• vertex 1, vertex 2;
• vertex 1, vertex 2, vertex 3.

Sample Input 2

4 6
1 2
1 3
1 4
2 3
2 4
3 4

Sample Output 2

16

Sample Input 3

8 21
2 6
1 3
5 6
3 8
3 6
4 7
4 6
3 4
1 5
2 4
1 2
2 7
1 4
3 5
2 5
2 3
4 5
3 7
6 7
5 7
2 8

Sample Output 3

2023

Problem Statement

Let the similarity f(X,Y) between two strings X and Y be the length of their longest common prefix.
For example, the similarity between abc and axbc is 1, and the similarity between aaa and aaaa is 3.

You are given a string S of length N. Let S_i be the suffix of S beginning with the i-th character of S. For each k=1,\ldots,N, find f(S_k,S_1)+f(S_k,S_2)+\ldots+f(S_k,S_N).

Constraints

• 1 \leq N \leq 10^6
• S is a string of length N consisting of lowercase English letters.

Sample Input 1

3
abb

Sample Output 1

3
3
2

S_1 is abb, S_2 is bb, and S_3 is b.

• For k=1: f(S_1,S_1)+f(S_1,S_2)+f(S_1,S_3)=3+0+0=3.
• For k=2: f(S_2,S_1)+f(S_2,S_2)+f(S_2,S_3)=0+2+1=3.
• For k=3: f(S_3,S_1)+f(S_3,S_2)+f(S_3,S_3)=0+1+1=2.

Sample Input 2

11
mississippi

Sample Output 2

11
16
14
12
13
11
9
7
4
3
4