Problem Statement

There is a two-dimensional plane. For integers r and c between 1 and 9, there is a pawn at the coordinates (r,c) if the c-th character of S_{r} is #, and nothing if the c-th character of S_{r} is ..

Find the number of squares in this plane with pawns placed at all four vertices.

Constraints

• Each of S_1,\ldots,S_9 is a string of length 9 consisting of # and ..

Sample Input 1

##.......
##.......
.........
.......#.
.....#...
........#
......#..
.........
.........

Sample Output 1

2

The square with vertices (1,1), (1,2), (2,2), and (2,1) have pawns placed at all four vertices.

The square with vertices (4,8), (5,6), (7,7), and (6,9) also have pawns placed at all four vertices.

Thus, the answer is 2.

Sample Input 2

.#.......
#.#......
.#.......
.........
....#.#.#
.........
....#.#.#
........#
.........

Sample Output 2

3

Problem Statement

You are given an integer sequence A=(A_1,A_2,\dots,A_N). You can perform the following operation any number of times (possibly zero).

• Choose integers i and j with 1\leq i,j \leq N. Decrease A_i by one and increase A_j by one.

Find the minimum number of operations required to make the difference between the minimum and maximum values of A at most one.

Constraints

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

Sample Input 1

4
4 7 3 7

Sample Output 1

3

By the following three operations, the difference between the minimum and maximum values of A becomes at most one.

• Choose i=2 and j=3 to make A=(4,6,4,7).
• Choose i=4 and j=1 to make A=(5,6,4,6).
• Choose i=4 and j=3 to make A=(5,6,5,5).

You cannot make the difference between maximum and minimum values of A at most one by less than three operations, so the answer is 3.

Sample Input 2

1
313

Sample Output 2

0

Sample Input 3

10
999999997 999999999 4 3 2 4 999999990 8 999999991 999999993

Sample Output 3

2499999974

Problem Statement

You run a web service with N users.

The i-th user with a current handle S_i wants to change it to T_i.
Here, S_1,\ldots, and S_N are pairwise distinct, and so are T_1,\ldots, and T_N.

Determine if there is an appropriate order to change their handles to fulfill all of their requests subject to the following conditions:

• you change only one user's handle at a time;
• you change each user's handle only once;
• when changing the handle, the new handle should not be used by other users at that point.

Constraints

• 1 \leq N \leq 10^5
• S_i and T_i are strings of length between 1 and 8 (inclusive) consisting of lowercase English letters.
• S_i \neq T_i
• S_i are pairwise distinct.
• T_i are pairwise distinct.

Sample Input 1

2
b m
m d

Sample Output 1

Yes

The 1-st user with a current handle b wants to change it to m.
The 2-nd user with a current handle m wants to change it to d.

First, you change the 2-nd user's handle from m to d; then you change the 1-st user's handle from b to m. This way, you can achieve the objective.

Note that you cannot change the 1-st user's handle to m at first, because it is used by the 2-nd user at that point.

Sample Input 2

3
a b
b c
c a

Sample Output 2

No

The 1-st user with a current handle a wants to change it to b.
The 2-nd user with a current handle b wants to change it to c.
The 3-rd user with a current handle c wants to change it to a.

We cannot change their handles subject to the conditions.

Sample Input 3

5
aaa bbb
yyy zzz
ccc ddd
xxx yyy
bbb ccc

Sample Output 3

Yes

Problem Statement

AtCoder in another world holds 10 types of contests called AAC, ..., AJC. There will be N contests from now on.
The types of these N contests are given to you as a string S: if the i-th character of S is x, the i-th contest will be AxC.
AtCoDeer will choose and participate in one or more contests from the N so that the following condition is satisfied.

• In the sequence of contests he will participate in, the contests of the same type are consecutive.
  • Formally, when AtCoDeer participates in x contests and the i-th of them is of type T_i, for every triple of integers (i,j,k) such that 1 \le i < j < k \le x, T_i=T_j must hold if T_i=T_k.

Find the number of ways for AtCoDeer to choose contests to participate in, modulo 998244353.
Two ways to choose contests are considered different when there is a contest c such that AtCoDeer participates in c in one way but not in the other.

Constraints

• 1 \le N \le 1000
• |S|=N
• S consists of uppercase English letters from A through J.

Sample Input 1

4
BGBH

Sample Output 1

13

For example, participating in the 1-st and 3-rd contests is valid, and so is participating in the 2-nd and 4-th contests.
On the other hand, participating in the 1-st, 2-nd, 3-rd, and 4-th contests is invalid, since the participations in ABCs are not consecutive, violating the condition for the triple (i,j,k)=(1,2,3).
Additionally, it is not allowed to participate in zero contests.
In total, there are 13 valid ways to participate in some contests.

Sample Input 2

100
BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBIEIJEIJIJCGCCFGIEBIHFCGFBFAEJIEJAJJHHEBBBJJJGJJJCCCBAAADCEHIIFEHHBGF

Sample Output 2

330219020

Be sure to find the count modulo 998244353.

Problem Statement

You are given two sequences of N numbers: A=(A_1,A_2,\ldots,A_N) and B=(B_1,B_2,\ldots,B_N).

Takahashi can repeat the following operation any number of times (possibly zero).

Choose three pairwise distinct integers i, j, and k between 1 and N.
Swap the i-th and j-th elements of A, and swap the i-th and k-th elements of B.

If there is a way for Takahashi to repeat the operation to make A and B equal, print Yes; otherwise, print No.
Here, A and B are said to be equal when, for every 1\leq i\leq N, the i-th element of A and that of B are equal.

Constraints

• 3 \leq N \leq 2\times 10^5
• 1\leq A_i,B_i\leq N
• All values in the input are integers.

Sample Input 1

3
1 2 1
1 1 2

Sample Output 1

Yes

Performing the operation once with (i,j,k)=(1,2,3) swaps A_1 and A_2, and swaps B_1 and B_3,
making both A and B equal to (2,1,1). Thus, you should print Yes.

Sample Input 2

3
1 2 2
1 1 2

Sample Output 2

No

There is no way to perform the operation to make A and B equal, so you should print No.

Sample Input 3

5
1 2 3 2 1
3 2 2 1 1

Sample Output 3

Yes

Sample Input 4

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

Sample Output 4

No