Problem Statement

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

Compute the value of \displaystyle \sum_{1\leq i< j\leq N} A_iA_j.

Constraints

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

Sample Input 1

3
4 2 3

Sample Output 1

26

We have \displaystyle \sum_{1\leq i< j\leq N} A_iA_j=A_1A_2+A_1A_3+A_2A_3=4\cdot 2+4\cdot 3+2\cdot 3=26.

Sample Input 2

2
9 45

Sample Output 2

405

Sample Input 3

10
7781 8803 8630 9065 8831 9182 8593 7660 7548 8617

Sample Output 3

3227530139

Problem Statement

You are given N pairs of integers (L_1, R_1), (L_2, R_2), \ldots, (L_N, R_N).

Determine whether there exists a sequence of N integers X = (X_1, X_2, \ldots, X_N) that satisfies the following conditions, and print one such sequence if it exists.

• L_i \leq X_i \leq R_i for each i = 1, 2, \ldots, N.
• \displaystyle \sum_{i=1}^N X_i = 0.

Constraints

• 1 \leq N \leq 2 \times 10^5
• -10^9 \leq L_i \leq R_i \leq 10^9
• All input values are integers.

Sample Input 1

3
3 5
-4 1
-2 3

Sample Output 1

Yes
4 -3 -1

The sequence X = (4, -3, -1) satisfies all the conditions. Other valid sequences include (3, -3, 0) and (5, -4, -1).

Sample Input 2

3
1 2
1 2
1 2

Sample Output 2

No

No sequence X satisfies the conditions.

Sample Input 3

6
-87 12
-60 -54
2 38
-76 6
87 96
-17 38

Sample Output 3

Yes
-66 -57 31 -6 89 9

Problem Statement

There is an N \times M grid and a player standing on it.
Let (i,j) denote the square at the i-th row from the top and j-th column from the left of this grid.
Each square of this grid is ice or rock, which is represented by N strings S_1,S_2,\dots,S_N of length M as follows:

• if the j-th character of S_i is ., square (i,j) is ice;
• if the j-th character of S_i is #, square (i,j) is rock.

The outer periphery of this grid (all squares in the 1-st row, N-th row, 1-st column, M-th column) is rock.

Initially, the player rests on the square (2,2), which is ice.
The player can make the following move zero or more times.

• First, specify the direction of movement: up, down, left, or right.
• Then, keep moving in that direction until the player bumps against a rock. Formally, keep doing the following:
  • if the next square in the direction of movement is ice, go to that square and keep moving;
  • if the next square in the direction of movement is rock, stay in the current square and stop moving.

Find the number of ice squares the player can touch (pass or rest on).

Constraints

• 3 \le N,M \le 200
• S_i is a string of length M consisting of # and ..
• Square (i, j) is rock if i=1, i=N, j=1, or j=M.
• Square (2,2) is ice.

Sample Input 1

6 6
######
#....#
#.#..#
#..#.#
#....#
######

Sample Output 1

12

For instance, the player can rest on (5,5) by moving as follows:

• (2,2) \rightarrow (5,2) \rightarrow (5,5).

The player can pass (2,4) by moving as follows:

• (2,2) \rightarrow (2,5), passing (2,4) in the process.

The player cannot pass or rest on (3,4).

Sample Input 2

21 25
#########################
#..............###...####
#..............#..#...###
#........###...#...#...##
#........#..#..#........#
#...##...#..#..#...#....#
#..#..#..###...#..#.....#
#..#..#..#..#..###......#
#..####..#..#...........#
#..#..#..###............#
#..#..#.................#
#........##.............#
#.......#..#............#
#..........#....#.......#
#........###...##....#..#
#..........#..#.#...##..#
#.......#..#....#..#.#..#
##.......##.....#....#..#
###.............#....#..#
####.................#..#
#########################

Sample Output 2

215

Problem Statement

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

Your goal is to perform the following operation repeatedly so that for every length-L contiguous subarray of A, the sum is a multiple of M.

• Choose an integer i such that 1 \leq i \leq N, and increase the value of A_i by 1.

Find the minimum possible number of operations before achieving the goal.

Constraints

• 1 \leq N, M \leq 500
• 1 \leq L \leq N
• 0 \leq A_i < M
• All input values are integers.

Sample Input 1

4 5 3
4 2 1 3

Sample Output 1

4

By performing the operation once choosing i = 2, twice choosing i = 3, and once choosing i = 4, you get A = (4, 3, 3, 4) with a total of four operations, where every length-3 contiguous subarray sums to a multiple of 5.

Sample Input 2

7 10 4
7 0 9 1 6 4 2

Sample Output 2

10

Problem Statement

The Republic of Atcoder has N towns numbered 1 through N, and M highways numbered 1 through M.
Highway i connects Town A_i and Town B_i bidirectionally.

King Takahashi is going to construct (N-M-1) new highways so that the following two conditions are satisfied:

• One can travel between every pair of towns using some number of highways
• For each i=1,\ldots,N, exactly D_i highways are directly connected to Town i

Determine if there is such a way of construction. If it exists, print one.

Constraints

• 2 \leq N \leq 2\times 10^5
• 0 \leq M \lt N-1
• 1 \leq D_i \leq N-1
• 1\leq A_i \lt B_i \leq N
• If i\neq j, then (A_i, B_i) \neq (A_j,B_j).
• All values in input are integers.

Sample Input 1

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

Sample Output 1

6 2
5 6
4 5

As in the Sample Output, the conditions can be satisfied by constructing highways connecting Towns 6 and 2, Towns 5 and 6, and Towns 4 and 5, respectively.

Another example to satisfy the conditions is to construct highways connecting Towns 6 and 4, Towns 5 and 6, and Towns 2 and 5, respectively.

Sample Input 2

5 1
1 1 1 1 4
2 3

Sample Output 2

-1

Sample Input 3

4 0
3 3 3 3

Sample Output 3

-1