Problem Statement

You are given patterns S and T consisting of # and ., each with H rows and W columns.
The pattern S is given as H strings, and the j-th character of S_i represents the element at the i-th row and j-th column. The same goes for T.

Determine whether S can be made equal to T by rearranging the columns of S.

Here, rearranging the columns of a pattern X is done as follows.

• Choose a permutation P=(P_1,P_2,\dots,P_W) of (1,2,\dots,W).
• Then, for every integer i such that 1 \le i \le H, simultaneously do the following.
  • For every integer j such that 1 \le j \le W, simultaneously replace the element at the i-th row and j-th column of X with the element at the i-th row and P_j-th column.

Constraints

• H and W are integers.
• 1 \le H,W
• 1 \le H \times W \le 4 \times 10^5
• S_i and T_i are strings of length W consisting of # and ..

Sample Input 1

3 4
##.#
##..
#...
.###
..##
...#

Sample Output 1

Yes

If you, for instance, arrange the 3-rd, 4-th, 2-nd, and 1-st columns of S in this order from left to right, S will be equal to T.

Sample Input 2

3 3
#.#
.#.
#.#
##.
##.
.#.

Sample Output 2

No

In this input, S cannot be made equal to T.

Sample Input 3

2 1
#
.
#
.

Sample Output 3

Yes

It is possible that S=T.

Sample Input 4

8 7
#..#..#
.##.##.
#..#..#
.##.##.
#..#..#
.##.##.
#..#..#
.##.##.
....###
####...
....###
####...
....###
####...
....###
####...

Sample Output 4

Yes

Problem Statement

We have a multiset of integers S, which is initially empty.

Given Q queries, process them in order. Each query is of one of the following types.

• 1 x: Insert an x into S.

• 2 x c: Remove an x from S m times, where m = \mathrm{min}(c,( the number of x's contained in S)).

• 3 : Print ( maximum value of S)-( minimum value of S). It is guaranteed that S is not empty when this query is given.

Constraints

• 1 \leq Q \leq 2\times 10^5
• 0 \leq x \leq 10^9
• 1 \leq c \leq Q
• When a query of type 3 is given, S is not empty.
• All values in input are integers.

Sample Input 1

8
1 3
1 2
3
1 2
1 7
3
2 2 3
3

Sample Output 1

1
5
4

The multiset S transitions as follows.

• 1-st query: insert 3 into S. S is now \lbrace 3 \rbrace.
• 2-nd query: insert 2 into S. S is now \lbrace 2, 3 \rbrace.
• 3-rd query: the maximum value of S = \lbrace 2, 3\rbrace is 3 and its minimum value is 2, so print 3-2=1.
• 4-th query: insert 2 into S. S is now \lbrace 2,2,3 \rbrace.
• 5-th query: insert 7 into S. S is now \lbrace 2, 2,3, 7\rbrace.
• 6-th query: the maximum value of S = \lbrace 2,2,3, 7\rbrace is 7 and its minimum value is 2, so print 7-2=5.
• 7-th query: since there are two 2's in S and \mathrm{min(2,3)} = 2, remove 2 from S twice. S is now \lbrace 3, 7\rbrace.
• 8-th query: the maximum value of S = \lbrace 3, 7\rbrace is 7 and its minimum value is 3, so print 7-3=4.

Sample Input 2

4
1 10000
1 1000
2 100 3
1 10

Sample Output 2

If the given queries do not contain that of type 3, nothing should be printed.

Problem Statement

We have an infinite hexagonal grid shown below. Initially, all squares are white.

A hexagonal cell is represented as (i,j) with two integers i and j.
Cell (i,j) is adjacent to the following six cells:

• (i-1,j-1)
• (i-1,j)
• (i,j-1)
• (i,j+1)
• (i+1,j)
• (i+1,j+1)

Takahashi has painted N cells (X_1,Y_1),(X_2,Y_2),\dots,(X_N,Y_N) black.
Find the number of connected components formed by the black cells.
Two black cells belong to the same connected component when one can travel between those two black cells by repeatedly moving to an adjacent black cell.

Constraints

• All values in the input are integers.
• 1 \le N \le 1000
• |X_i|,|Y_i| \le 1000
• The pairs (X_i,Y_i) are distinct.

Sample Input 1

6
-1 -1
0 1
0 2
1 0
1 2
2 0

Sample Output 1

3

After Takahashi paints cells black, the grid looks as shown below.

The black squares form the following three connected components:

• (-1,-1)
• (1,0),(2,0)
• (0,1),(0,2),(1,2)

Sample Input 2

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

Sample Output 2

4

Sample Input 3

5
2 1
2 -1
1 0
3 1
1 -1

Sample Output 3

1

Problem Statement

You are given a tree with N vertices. The vertices are numbered 1 to N, and the i-th edge connects vertices A_i and B_i.

You are also given a sequence of positive integers C = (C_1, C_2, \ldots ,C_N) of length N. Let d(a, b) be the number of edges between vertices a and b, and for x = 1, 2, \ldots, N, let \displaystyle f(x) = \sum_{i=1}^{N} (C_i \times d(x, i)). Find \displaystyle \min_{1 \leq v \leq N} f(v).

Constraints

• 1 \leq N \leq 10^5
• 1 \leq A_i, B_i \leq N
• The given graph is a tree.
• 1 \leq C_i \leq 10^9

Sample Input 1

4
1 2
1 3
2 4
1 1 1 2

Sample Output 1

5

For example, consider calculating f(1). We have d(1, 1) = 0, d(1, 2) = 1, d(1, 3) = 1, d(1, 4) = 2.
Thus, f(1) = 0 \times 1 + 1 \times 1 + 1 \times 1 + 2 \times 2 = 6.

Similarly, f(2) = 5, f(3) = 9, f(4) = 6. Since f(2) is the minimum, print 5.

Sample Input 2

2
2 1
1 1000000000

Sample Output 2

1

f(2) = 1, which is the minimum.

Sample Input 3

7
7 3
2 5
2 4
3 1
3 6
2 1
2 7 6 9 3 4 6

Sample Output 3

56

Problem Statement

Takahashi and a cargo are on a coordinate plane.

Takahashi is currently at (X_A,Y_A), and the cargo is at (X_B,Y_B). He wants to move the cargo to (X_C,Y_C).

When he is at (x,y), he can make one of the following moves in a single action.

• Move to (x+1,y). If the cargo is at (x+1,y) before the move, move it to (x+2,y).
• Move to (x-1,y). If the cargo is at (x-1,y) before the move, move it to (x-2,y).
• Move to (x,y+1). If the cargo is at (x,y+1) before the move, move it to (x,y+2).
• Move to (x,y-1). If the cargo is at (x,y-1) before the move, move it to (x,y-2).

Find the minimum number of actions required to move the cargo to (X_C,Y_C).

Constraints

• -10^{17}\leq X_A,Y_A,X_B,Y_B,X_C,Y_C\leq 10^{17}
• (X_A,Y_A)\neq (X_B,Y_B)
• (X_B,Y_B)\neq (X_C,Y_C)
• All input values are integers.

Sample Input 1

1 2 3 3 0 5

Sample Output 1

9

Takahashi can move the cargo to (0,5) in nine actions as follows.

• Move to (2,2).
• Move to (3,2).
• Move to (3,3). The cargo moves to (3,4).
• Move to (3,4). The cargo moves to (3,5).
• Move to (4,4).
• Move to (4,5).
• Move to (3,5). The cargo moves to (2,5).
• Move to (2,5). The cargo moves to (1,5).
• Move to (1,5). The cargo moves to (0,5).

It is impossible to move the cargo to (0,5) in eight or fewer actions, so you should print 9.

Sample Input 2

0 0 1 0 -1 0

Sample Output 2

6

Sample Input 3

-100000000000000000 -100000000000000000 100000000000000000 100000000000000000 -100000000000000000 -100000000000000000

Sample Output 3

800000000000000003