Problem Statement

You are given integers A, B, C. If A \neq B and B = C, output Yes; otherwise, output No.

Constraints

• 1 \leq A, B, C \leq 9
• All input values are integers.

Sample Input 1

4 5 5

Sample Output 1

Yes

Since 4 \neq 5 and 5 = 5, output Yes.

Sample Input 2

1 3 7

Sample Output 2

No

Although 1 \neq 3, we don't have 3 = 7, so output No.

Sample Input 3

6 6 6

Sample Output 3

No

Problem Statement

There is a grid with H rows and W columns. The cell at the i-th row from the top and j-th column from the left is denoted as cell (i, j).

Each cell of the grid is colored white or black. The information of the grid is given by H strings S_1, S_2, \ldots, S_H each of length W: cell (i, j) is white if the j-th character of S_i is ., and black if it is #.

Find the number of rectangular regions of the grid that are point-symmetrically colored.

More formally, find the number of integer tuples (h_1, h_2, w_1, w_2) satisfying all of the following conditions:

• 1 \leq h_1 \leq h_2 \leq H
• 1 \leq w_1 \leq w_2 \leq W
• For all integers i, j satisfying h_1 \leq i \leq h_2 and w_1 \leq j \leq w_2, cell (i, j) and cell (h_1 + h_2 - i, w_1 + w_2 - j) have the same color.

Constraints

• 1 \leq H, W \leq 10
• H and W are integers.
• S_i is a string of length W consisting of . and #.

Sample Input 1

3 2
.#
#.
##

Sample Output 1

10

As shown in the figure above, the answer is 10.

Sample Input 2

4 5
.#.#.
####.
##..#
....#

Sample Output 2

54

Problem Statement

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

Find the minimum possible sum of all elements of A after performing the following operation exactly K times.

• Choose an integer x. For each i such that A_i = x, replace the value of A_i with 0.

Constraints

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

Sample Input 1

6 2
7 2 7 2 2 9

Sample Output 1

6

Initially, A = (7, 2, 7, 2, 2, 9).

Performing the operation with x = 9 gives A = (7, 2, 7, 2, 2, 0).

Next, performing the operation with x = 7 gives A = (0, 2, 0, 2, 2, 0).

At this point, the sum of all elements of A is 0 + 2 + 0 + 2 + 2 + 0 = 6.

Sample Input 2

8 6
1 2 3 4 1 2 3 4

Sample Output 2

0

Sample Input 3

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

Sample Output 3

8

Problem Statement

There are N cards and N piles of cards.

The cards and the piles are numbered 1, 2, \ldots, N. Initially, pile i contains only card i.

Perform the following operation for each i = 1, 2, \ldots, Q in order:

• Move card C_i and all cards stacked on top of card C_i, preserving their order, on top of card P_i. It is guaranteed that immediately before performing the operation, cards C_i and P_i are in different piles, and card P_i is on top of some pile.

Find the number of cards in each pile after all operations are completed.

Constraints

• 1 \leq N, Q \leq 3 \times 10^5
• 1 \leq C_i, P_i \leq N
• When the operations are performed in order, immediately before each operation, cards C_i and P_i are in different piles.
• When the operations are performed in order, immediately before each operation, card P_i is on top of some pile.
• All input values are integers.

Sample Input 1

5 4
1 3
4 5
1 4
4 2

Sample Output 1

0 3 1 0 1

The sequence of operations proceeds as shown in the figure below.

Sample Input 2

7 8
3 1
5 4
2 5
5 7
2 3
6 2
3 4
5 1

Sample Output 2

2 0 0 4 0 0 1

Problem Statement

You are given a string S of length N consisting of the three characters A, B, and C.
There are \frac{N(N+1)}{2} non-empty substrings of S; find how many of them satisfy the following condition:

• The numbers of occurrences of A, B, and C are all distinct from each other.

Count two substrings separately if they are taken from different positions in S, even if they are identical as strings.

Constraints

• 1 \leq N \leq 2 \times 10^5
• |S|=N
• N is an integer.
• S is a string consisting of the three characters A, B, and C.

Sample Input 1

6
AABBCC

Sample Output 1

4

Deleting 0 characters from the beginning and 3 characters from the end of S gives AAB, which satisfies the condition.
Deleting 1 character from the beginning and 2 characters from the end of S gives ABB, which satisfies the condition.
Deleting 2 characters from the beginning and 1 character from the end of S gives BBC, which satisfies the condition.
Deleting 3 characters from the beginning and 0 characters from the end of S gives BCC, which satisfies the condition.
No other substrings satisfy the condition.

Sample Input 2

6
ABCABC

Sample Output 2

0

No substring satisfies the condition.

Sample Input 3

10
ACABCAABAB

Sample Output 3

17

Problem Statement

There is a sequence A of N non-negative integers, all initially 0. Process Q queries given in order.
For the q-th query, you are given integers l_q, r_q satisfying 1 \leq l_q \leq r_q \leq N and a positive integer a_q. Perform the following in order:

• Add a_q to each of A_{l_q}, A_{{l_q}+1}, \dots, A_{r_q}.
• Then, letting M=r_q-l_q+1 and B=(B_1,B_2,\dots,B_M)=(A_{l_q}, A_{l_q+1}, \dots, A_{r_q}), find the answer to the following problem:

There are M slimes 1,2,\dots,M, where the m-th slime has weight B_m.
Repeat the operation of choosing two slimes and merging them M-1 times.
When slimes of weights x and y are merged, a slime of weight x+y appears and the original two slimes disappear. This incurs a cost of x \times y.
Find, modulo 998244353, the minimum possible total cost of the M-1 operations.

Note that the changes made on A in each query carry over to subsequent queries.

Constraints

• 1 \leq N \leq 10^5
• 1 \leq Q \leq 10^5
• 1 \leq l_q \leq r_q \leq N
• 1 \leq a_q \leq 10^9
• All input values are integers.

Sample Input 1

5 4
1 3 22
3 4 13
5 5 455
1 5 1000000000

Sample Output 1

1452
455
0
21421644

After the first query, A=(22,22,22,0,0) and B=(22,22,22). Merging the first and third slimes first incurs a cost of 22 \times 22=484. Then merging the remaining two slimes incurs a cost of 22 \times 44=968. The total cost is 484+968=1452. Moreover, the total cost cannot be made smaller than this.
After the second query, A=(22,22,35,13,0) and B=(35,13). The answer is 35 \times 13 = 455.

Problem Statement

You are given a sequence A of N positive integers.
Among the \frac{N(N+1)}{2} non-empty (contiguous) subarrays of A, we call a sequence X a balanced sequence if and only if it satisfies the following condition:

• Every integer appearing in X appears the same number of times in X.

For each k=1,2,\dots,K, find the following two values:

• The number of balanced sequences in which each integer appears exactly B_k times.
• The number of balanced sequences in which exactly B_k distinct integers appear.

Count two subarrays separately if they are taken from different positions in A, even if they are identical as sequences.

Solve T test cases per input.

Constraints

• 1 \leq T \leq 2 \times 10^5
• 1 \leq N \leq 2 \times 10^5
• 1 \leq K \leq \min(N,10)
• 1 \leq A_i \leq N
• 1 \leq B_k \leq N
• B_1,B_2,\dots,B_K are pairwise distinct.
• The sum of N over all test cases is at most 2 \times 10^5.
• All input values are integers.

Sample Input 1

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

Sample Output 1

1 4
7 4
1 1
13 8
3 8
1 1
0 0
0 0
0 0
0 0

For the first test case, the pairs (l,r) such that the subarray of A from the l-th through the r-th element is a balanced sequence are (1,1),(1,2),(1,4),(2,2),(2,3),(3,3),(3,4),(4,4), giving eight instances in total.
Among these, the ones in which each integer appears exactly twice are (1,4), giving one instance, and the ones in which exactly two distinct integers appear are (1,2),(1,4),(2,3),(3,4), giving four instances.
Thus, for k=1, output 1 4.
Also, the ones in which each integer appears exactly once are (1,1),(1,2),(2,2),(2,3),(3,3),(3,4),(4,4), giving seven instances, and the ones in which exactly one distinct integer appears are (1,1),(2,2),(3,3),(4,4), giving four instances.
Thus, for k=2, output 7 4.