Problem Statement

You are given a positive integer N and two strings S and T, each of length N and consisting of lowercase English letters.

Find the Hamming distance between S and T. That is, find the number of integers i such that 1 \leq i \leq N and the i-th character of S is different from the i-th character of T.

Constraints

• 1\leq N \leq 100
• N is an integer.
• Each of S and T is a string of length N consisting of lowercase English letters.

Sample Input 1

6
abcarc
agcahc

Sample Output 1

2

S and T differ in the 2nd and 5th characters, but not in other characters. Thus, the answer is 2.

Sample Input 2

7
atcoder
contest

Sample Output 2

7

Sample Input 3

8
chokudai
chokudai

Sample Output 3

0

Sample Input 4

10
vexknuampx
vzxikuamlx

Sample Output 4

4

Problem Statement

You are given N pairs of integers: (A_1, B_1), (A_2, B_2), \ldots, (A_N, B_N). For each i = 1, 2, \ldots, N, print A_i + B_i.

Constraints

• 1 \leq N \leq 1000
• -10^9 \leq A_i, B_i \leq 10^9
• All values in the input are integers.

Sample Input 1

4
3 5
2 -6
-5 0
314159265 123456789

Sample Output 1

8
-4
-5
437616054

• The first line should contain A_1 + B_1 = 3 + 5 = 8.
• The second line should contain A_2 + B_2 = 2 + (-6) = -4.
• The third line should contain A_3 + B_3 = (-5) + 0 = -5.
• The fourth line should contain A_4 + B_4 = 314159265 + 123456789 = 437616054.

Problem Statement

In this problem, an input file contains multiple test cases.
You are first given an integer T. Solve the following problem for T test cases.

• We have N positive integers A_1, A_2, ..., A_N. How many of them are odd?

Constraints

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

Sample Input 1

4
3
1 2 3
2
20 23
10
6 10 4 1 5 9 8 6 5 1
1
1000000000

Sample Output 1

2
1
5
0

This input contains four test cases.

The second and third lines correspond to the first test case, where N = 3, A_1 = 1, A_2 = 2, A_3 = 3.
We have two odd numbers in A_1, A_2, and A_3, so the first line should contain 2.

Problem Statement

There is a grid with H rows from top to bottom and W columns from left to right. Let (i, j) denote the square at the i-th row from the top and j-th column from the left.
The squares are described by characters C_{i,j}. If C_{i,j} is ., (i, j) is empty; if it is #, (i, j) contains a box.

For integers j satisfying 1 \leq j \leq W, let the integer X_j defined as follows.

• X_j is the number of boxes in the j-th column. In other words, X_j is the number of integers i such that C_{i,j} is #.

Find all of X_1, X_2, \dots, X_W.

Constraints

• 1 \leq H \leq 1000
• 1 \leq W \leq 1000
• H and W are integers.
• C_{i, j} is . or #.

Sample Input 1

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

Sample Output 1

1 2 0 3

In the 1-st column, one square, (1, 1), contains a box. Thus, X_1 = 1.
In the 2-nd column, two squares, (2, 2) and (3, 2), contain a box. Thus, X_2 = 2.
In the 3-rd column, no squares contain a box. Thus, X_3 = 0.
In the 4-th column, three squares, (1, 4), (2, 4), and (3, 4), contain a box. Thus, X_4 = 3.
Therefore, the answer is (X_1, X_2, X_3, X_4) = (1, 2, 0, 3).

Sample Input 2

3 7
.......
.......
.......

Sample Output 2

0 0 0 0 0 0 0

There may be no square that contains a box.

Sample Input 3

8 3
.#.
###
.#.
.#.
.##
..#
##.
.##

Sample Output 3

2 7 4

Sample Input 4

5 47
.#..#..#####..#...#..#####..#...#...###...#####
.#.#...#.......#.#...#......##..#..#...#..#....
.##....#####....#....#####..#.#.#..#......#####
.#.#...#........#....#......#..##..#...#..#....
.#..#..#####....#....#####..#...#...###...#####

Sample Output 4

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

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 strings S_1,S_2,\dots,S_N consisting of lowercase English alphabets.

Consider choosing some number of strings from S_1,S_2,\dots,S_N.

Find the maximum number of distinct alphabets that satisfy the following condition: "the alphabet is contained in exactly K of the chosen strings."

Constraints

• 1 \le N \le 15
• 1 \le K \le N
• N and K are integers.
• S_i is a non-empty string consisting of lowercase English alphabets.
• For each integer i such that 1 \le i \le N, S_i does not contain two or more same alphabets.
• If i \neq j, then S_i \neq S_j.

Sample Input 1

4 2
abi
aef
bc
acg

Sample Output 1

3

When S_1,S_3, and S_4 are chosen, a,b, and c occur in exactly two of the strings.

There is no way to choose strings so that 4 or more alphabets occur in exactly 2 of the strings, so the answer is 3.

Sample Input 2

2 2
a
b

Sample Output 2

0

You cannot choose the same string more than once.

Sample Input 3

5 2
abpqxyz
az
pq
bc
cy

Sample Output 3

7

Problem Statement

There is an election to choose one winner from N candidates with candidate numbers 1, 2, \ldots, N, and there have been M votes cast.

Each vote is for exactly one candidate, with the i-th vote being for candidate A_i.

The votes will be counted in order from first to last, and after each vote is counted, the current winner will be updated and displayed.

The candidate with the most votes among those counted is the winner. If there are multiple candidates with the most votes, the one with the smallest candidate number is the winner.

For each i = 1, 2, \ldots, M, determine the winner when counting only the first i votes.

Constraints

• 1 \leq N, M \leq 200000
• 1 \leq A_i \leq N
• All input values are integers.

Sample Input 1

3 7
1 2 2 3 1 3 3

Sample Output 1

1
1
2
2
1
1
3

Let C_i denote the number of votes for candidate i.

• After the first vote is counted, (C_1, C_2, C_3) = (1, 0, 0), so the winner is 1.
• After the second vote is counted, (C_1, C_2, C_3) = (1, 1, 0), so the winner is 1.
• After the third vote is counted, (C_1, C_2, C_3) = (1, 2, 0), so the winner is 2.
• After the fourth vote is counted, (C_1, C_2, C_3) = (1, 2, 1), so the winner is 2.
• After the fifth vote is counted, (C_1, C_2, C_3) = (2, 2, 1), so the winner is 1.
• After the sixth vote is counted, (C_1, C_2, C_3) = (2, 2, 2), so the winner is 1.
• After the seventh vote is counted, (C_1, C_2, C_3) = (2, 2, 3), so the winner is 3.

Sample Input 2

100 5
100 90 80 70 60

Sample Output 2

100
90
80
70
60

Sample Input 3

9 8
8 8 2 2 8 8 2 2

Sample Output 3

8
8
8
2
8
8
8
2

Problem Statement

Takahashi will embark on an adventure.

During the adventure, N events will occur. The i-th event (1\leq i\leq N) is represented by a pair of integers (t _ i,x _ i) (1\leq t _ i\leq 2,1\leq x _ i\leq N) and is as follows:

• If t _ i=1, he finds one potion of type x _ i. He can choose to pick it up or discard it.
• If t _ i=2, he encounters one monster of type x _ i. If he has a potion of type x _ i, he can use one to defeat the monster. If he does not defeat it, he will be defeated.

Determine whether he can defeat all the monsters without being defeated.

If he cannot defeat all the monsters, print -1.

Otherwise, let K be the maximum number of potions he has at some point during the adventure. Let K _ {\min} be the minimum value of K across all strategies where he will not be defeated. Print the value of K _ {\min} and the actions of Takahashi that achieve K _ {\min}.

Constraints

• 1\leq N\leq2\times10^5
• 1\leq t _ i\leq2\ (1\leq i\leq N)
• 1\leq x _ i\leq N\ (1\leq i\leq N)
• All input values are integers.

Sample Input 1

13
1 2
1 3
1 1
1 3
1 2
2 3
1 3
1 3
2 3
1 3
2 2
2 3
2 1

Sample Output 1

3
1 1 1 0 0 1 0 1

The sample output corresponds to the following actions:

• Find potions of types 2,3,1 in this order. Pick up all of them.
• Find potions of types 3,2 in this order. Do not pick up any of them.
• Encounter a type-3 monster. Use one type-3 potion to defeat it.
• Find a type-3 potion. Pick it up.
• Find a type-3 potion. Do not pick it up.
• Encounter a type-3 monster. Use one type-3 potion to defeat it.
• Find a type-3 potion. Pick it up.
• Encounter a type-2 monster. Use one type-2 potion to defeat it.
• Encounter a type-3 monster. Use one type-3 potion to defeat it.
• Encounter a type-1 monster. Use one type-1 potion to defeat it.

In this sequence of actions, the value of K is 3.

There is no way to avoid defeat with K\leq 2, so the sought value of K _ {\min} is 3. There are multiple sequences of actions that satisfy K=3 and allow him to avoid defeat; you may print any of them.

Sample Input 2

4
2 3
1 4
2 1
1 2

Sample Output 2

-1

He will inevitably be defeated by the first monster he encounters.

Sample Input 3

30
1 25
1 2
1 10
1 18
2 18
1 11
2 11
1 21
1 6
2 2
2 10
1 11
1 24
1 11
1 3
1 2
1 18
2 25
1 8
1 10
1 11
2 18
2 10
1 10
2 2
1 24
1 10
2 10
1 25
2 6

Sample Output 3

4
1 1 1 1 1 0 1 0 0 0 0 1 1 0 1 0 1 0 0 0

Problem Statement

There is a grid with H rows and W columns. The cell at the r-th row from the top and c-th column from the left is called cell (r,c). Each cell is painted black or white: cell (R_k,C_k) is black for k=1,2,\ldots,N, and the remaining HW-N cells are white.

Find the number of rectangular regions in this grid with h rows and w columns such that all cells contained in them are painted white.

More formally, find the number of pairs of integers (r_0, c_0) satisfying all of the following conditions:

• 1\le r_0 \le H-h+1
• 1\le c_0 \le W-w+1
• Cell (r_0+i,c_0+j) is painted white for all pairs of integers (i,j) satisfying 0\le i< h,\ 0\le j< w.

Constraints

• 1\le h\le H\le 10^9
• 1\le w\le W\le 10^9
• 0\le N\le 2\times 10^5
• 1\le R_k\le H
• 1\le C_k\le W
• (R_{k_1},C_{k_1}) \neq (R_{k_2},C_{k_2}) (k_1 \neq k_2)
• All input values are integers.

Sample Input 1

3 4 2 2 3
1 3
2 4
3 1

Sample Output 1

2

The two rectangular regions enclosed in red in the figure below satisfy all the conditions.

Sample Input 2

4 4 3 2 2
2 2
3 4

Sample Output 2

0

No rectangular region satisfies all the conditions.

Sample Input 3

449 449 3 14 0

Sample Output 3

194892

Sample Input 4

31 9 5 7 10
14 8
8 4
18 8
12 1
8 5
9 6
18 1
14 7
5 6
26 7

Sample Output 4

12