Problem Statement

On a certain planet, a year has D days, and contests are held every 7 days. Contests never span across days.

The first contest of a certain year was held on the F-th day of the year. On what day of the next year will the first contest of the next year be held?

The constraints of this problem guarantee that at least one contest will be held in the next year.

Constraints

• 10 \leq D \leq 366
• 1 \leq F \leq 7
• All input values are integers.

Sample Input 1

365 4

Sample Output 1

3

If the first contest of a certain year was held on the 4th day of the year, the first contest of the next year will be held on the 3rd day of the year.

Sample Input 2

10 5

Sample Output 2

2

Problem Statement

You are given integers N and M, a digit string S of length N, and a digit string T of length M. Here, a digit string is a string consisting of digits from 0 to 9.

You can perform the following operation zero or more times:

• Choose one character from T and increase the chosen digit by 1. However, if the chosen digit is 9, change it to 0.

Find the minimum number of operations required to make T a substring (contiguous subsequence) of S.

Constraints

• 1\le M\le N\le 100
• N and M are integers.
• S is a digit string of length N.
• T is a digit string of length M.

Sample Input 1

4 2
2025
91

Sample Output 1

2

You can make T a substring of S with two operations as follows:

• Perform the operation on the 2nd character of T. T= 91 becomes T= 92.
• Perform the operation on the 1st character of T. T= 92 becomes T= 02.

02 is a substring from the 2nd character to the 3rd character of S.

It is impossible to make T a substring of S with less than two operations, so output 2.

Sample Input 2

3 2
438
38

Sample Output 2

0

38 is a substring of 438 from the beginning. Thus, output 0.

Sample Input 3

5 5
00000
11111

Sample Output 3

45

Sample Input 4

8 3
20251227
438

Sample Output 4

13

Problem Statement

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

You can perform the following operation zero or more times in any order:

• Choose an integer k between 1 and |A|-3, inclusive, such that A_k=A_{k+1}=A_{k+2}=A_{k+3}, and remove A_k,A_{k+1},A_{k+2},A_{k+3} from A. (More formally, replace A with (A_1,A_2,\ldots,A_{k-1},A_{k+4},A_{k+5},\ldots,A_N).)

Here, |A| represents the length of the integer sequence A.

Find the minimum possible value of the final |A| after repeating the operation.

Constraints

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

Sample Input 1

10
1 1 1 4 4 4 4 1 2 3

Sample Output 1

2

You can make |A|=2 with two operations as follows:

• Choose k=4. This choice is valid since A_4=A_5=A_6=A_7=4 holds. A=(1,1,1,1,2,3) is obtained.
• Choose k=1. This choice is valid since A_1=A_2=A_3=A_4=1 holds. A=(2,3) is obtained.

It is impossible to make |A| less than 2, so output 2.

Sample Input 2

3
2 1 3

Sample Output 2

3

You cannot perform any operation from the beginning.

Sample Input 3

13
1 1 4 4 4 1 1 1 1 4 1 4 1

Sample Output 3

5

Problem Statement

Snuke is observing a snake and is curious about which parts are the head, body, and tail. He divided the snake into N blocks and evaluated the head-likeness, body-likeness, and tail-likeness of each block. Then, he decided to find the division that maximizes the sum of the likeness values.

You are given length-N integer sequences A = (A_1, A_2, \ldots, A_N), B = (B_1, B_2, \ldots, B_N), and C = (C_1, C_2, \ldots, C_N).

Find the maximum possible value of \displaystyle\sum_{i = 1}^{x} A_i + \sum_{i = x + 1}^{y} B_i + \sum_{i = y + 1}^{N} C_i for a pair of integers (x, y) satisfying 1 \leq x < y < N.

Constraints

• 3 \leq N \leq 3 \times 10^5
• 1 \leq A_i, B_i, C_i \leq 10^6
• All input values are integers.

Sample Input 1

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

Sample Output 1

16

With (x, y) = (2, 3), we have \displaystyle\sum_{i = 1}^{x} A_i + \sum_{i = x + 1}^{y} B_i + \sum_{i = y + 1}^{N} C_i = 1 + 4 + 4 + 4 + 3 = 16.

Sample Input 2

3
1 1 1
1 1 1
1 1 1

Sample Output 2

3

Sample Input 3

6
2 10 7 7 7 11
5 7 9 10 9 12
6 6 7 10 12 7

Sample Output 3

50

Problem Statement

There are N people and N buckets. Both the people and buckets are numbered 1, 2, \ldots, N.

Initially, person i holds only bucket i, and bucket i is empty.

From now on, the following operation will be performed 10^9 times:

• For i = 1, 2, \ldots, N simultaneously, person i adds i units of water to each of the buckets they are holding and passes those buckets to person A_i.

Here, there is no limit on the amount of water that can be put in a bucket.

For i = 1, 2, \ldots, Q, answer the following queries:

• Find the amount of water in bucket B_i immediately after the T_i-th operation.

Constraints

• 2 \leq N \leq 2 \times 10^5
• 1 \leq Q \leq 2 \times 10^5
• 1 \leq A_i \leq N
• 1 \leq T_i \leq 10^9
• 1 \leq B_i \leq N
• All input values are integers.

Sample Input 1

5 6
3 4 2 2 5
4 3
6 5
1 4
10 1
10 2
1000000000 1

Sample Output 1

11
30
4
28
30
2999999998

We will explain the first query.

Initially, bucket 3 is held by person 3.

Immediately after the 1-st operation, bucket 3 is held by person 2 and contains 3 units of water.

Immediately after the 2-nd operation, bucket 3 is held by person 4 and contains 5 units of water.

Immediately after the 3-rd operation, bucket 3 is held by person 2 and contains 9 units of water.

Immediately after the 4-th operation, bucket 3 is held by person 4 and contains 11 units of water.

Thus, the answer to the first query is 11.

Problem Statement

You are given a tree T with N vertices. The vertices are numbered from 0 to N-1, and the i-th edge (1\le i\le N-1) bidirectionally connects vertices u_i and v_i. (Note that vertex numbers are 0-indexed and edge numbers are 1-indexed.)

For a pair of integers (i,j) where 0 \leq i,j < N, define f(i,j) as follows:

• The vertex number of the vertex with the smallest number among the vertices not included in the path from vertex i to vertex j in tree T.
  • Here, if the path from vertex i to vertex j includes all vertices from vertex 0 to vertex N-1, let f(i,j)=N.

Note that the path from vertex i to vertex j in tree T includes vertices i and j.

Find the value of \displaystyle \sum_{0\le i \le j < N} f(i,j).

Constraints

• 2\le N\le 2\times 10^5
• 0\le u_i < v_i < N
• The graph given in the input is a tree.
• All input values are integers.

Sample Input 1

2
0 1

Sample Output 1

3

We have f(0,0)=1,f(0,1)=2,f(1,1)=0. Thus, output 1+2+0=3.

Sample Input 2

5
0 1
0 2
2 3
2 4

Sample Output 2

16

Sample Input 3

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

Sample Output 3

16

Problem Statement

You are given integers N,M,K, a length-N integer sequence A=(A_0,A_1,\ldots,A_{N-1}), and a length-M integer sequence B=(B_0,B_1,\ldots,B_{M-1}). Note that the indices start from 0.

Find \displaystyle\sum_{i=0}^{K-1} \min(A_{i\bmod N}, B_{i \bmod M}) , modulo 998244353.

Constraints

• 1\le N,M\le 2\times 10^5
• 1\le K\le 10^{18}
• 1\le A_i,B_i\le 10^9
• All input values are integers.

Sample Input 1

3 2 5
3 1 4
1 5

Sample Output 1

7

The desired value is \min(3,1)+\min(1,5)+\min(4,1)+\min(3,5)+\min(1,1)=7.

Sample Input 2

4 4 27
6 1 10 42
87 6 21 33

Sample Output 2

317

Sample Input 3

5 7 583272014892537201
763832259 547096173 408327452 685495693 212251318
850800766 845647066 240229336 648345577 691868483 740301913 740485849

Sample Output 3

931208848

Compute modulo 998244353.