Problem Statement

You have N socks. The color of the i-th sock is A_i.

You want to perform the following operation as many times as possible. How many times can it be performed at most?

• Choose two same-colored socks that are not paired yet, and pair them.

Constraints

• 1\leq N \leq 5\times 10^5
• 1\leq A_i \leq 10^9
• All values in the input are integers.

Sample Input 1

6
4 1 7 4 1 4

Sample Output 1

2

You can do the operation twice as follows.

• Choose two socks with the color 1 and pair them.
• Choose two socks with the color 4 and pair them.

Then, you will be left with one sock with the color 4 and another with the color 7, so you can no longer do the operation. There is no way to do the operation three or more times, so you should print 2.

Sample Input 2

1
158260522

Sample Output 2

0

Sample Input 3

10
295 2 29 295 29 2 29 295 2 29

Sample Output 3

4

Problem Statement

You are given a sequence A=(A_1,A_2,\ldots,A_N) of length N consisting of non-negative integers.

Determine if there is an even number represented as the sum of two different elements of A. If it exists, find the maximum such number.

Constraints

• 2\leq N \leq 2\times 10^5
• 0\leq A_i\leq 10^9
• The elements of A are distinct.
• All values in the input are integers.

Sample Input 1

3
2 3 4

Sample Output 1

6

The values represented as the sum of two distinct elements of A are 5, 6, and 7. We have an even number here, and the maximum is 6.

Sample Input 2

2
1 0

Sample Output 2

-1

The value represented as the sum of two distinct elements of A is 1. We have no even number here, so -1 should be printed.

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 simple undirected graph with N vertices and M edges. The i-th edge connects Vertices U_i and V_i. Vertex i has a positive integer A_i written on it.

You will repeat the following operation N times.

• Choose a Vertex x that is not removed yet, and remove Vertex x and all edges incident to Vertex x. The cost of this operation is the sum of the integers written on the vertices directly connected by an edge with Vertex x that are not removed yet.

We define the cost of the entire N operations as the maximum of the costs of the individual operations. Find the minimum possible cost of the entire operations.

Constraints

• 1 \le N \le 2 \times 10^5
• 0 \le M \le 2 \times 10^5
• 1 \le A_i \le 10^9
• 1 \le U_i,V_i \le N
• The given graph is simple.
• All values in input are integers.

Sample Input 1

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

Sample Output 1

3

By performing the operations as follows, the maximum of the costs of the N operations can be 3.

• Choose Vertex 3. The cost is A_1=3.
• Choose Vertex 1. The cost is A_2+A_4=3.
• Choose Vertex 2. The cost is 0.
• Choose Vertex 4. The cost is 0.

The maximum of the costs of the N operations cannot be 2 or less, so the solution is 3.

Sample Input 2

7 13
464 661 847 514 74 200 188
5 1
7 1
5 7
4 1
4 5
2 4
5 2
1 3
1 6
3 5
1 2
4 6
2 7

Sample Output 2

1199

Problem Statement

There is a cleaning robot on the square (0, 0) in an infinite two-dimensional grid.

The robot will be given a program represented as a string consisting of four kind of characters L, R, U, D.
It will read the characters in the program from left to right and perform the following action for each character read.

1. Let (x, y) be the square where the robot is currently on.
2. Make the following move according to the character read:
   • if L is read: go to (x-1, y).
   • if R is read: go to (x+1, y).
   • if U is read: go to (x, y-1).
   • if D is read: go to (x, y+1).

You are given a string S consisting of L, R, U, D. The program that will be executed by the robot is the concatenation of K copies of S.

Squares visited by the robot at least once, including the initial position (0, 0), will be cleaned.
Print the number of squares that will be cleaned at the end of the execution of the program.

Constraints

• S is a string of length between 1 and 2 \times 10^5 (inclusive) consisting of L, R, U, D.
• 1 \leq K \leq 10^{12}

Sample Input 1

RDRUL
2

Sample Output 1

7

The robot will execute the program RDRULRDRUL. It will start on (0, 0) and travel as follows:
(0, 0) \rightarrow (1, 0) \rightarrow (1, 1) \rightarrow (2, 1) \rightarrow (2, 0) \rightarrow (1, 0) \rightarrow (2, 0) \rightarrow (2, 1) \rightarrow (3, 1) \rightarrow (3, 0) \rightarrow (2, 0).
In the end, seven squares will get cleaned: (0, 0), (1, 0), (1, 1), (2, 0), (2, 1), (3, 0), (3, 1).

Sample Input 2

LR
1000000000000

Sample Output 2

2

Sample Input 3

UUURRDDDRRRUUUURDLLUURRRDDDDDDLLLLLLU
31415926535

Sample Output 3

219911485785