CodeEff/ECCO huggingface dataset:
Problem Description: Score : 100 points
Problem Statement
You are given an array
a_0, a_1, ..., a_{N-1}
of length
N
. Process
Q
queries of the following types.
0 l r b c
: For each
i = l, l+1, \dots, {r - 1}
, set
a_i \gets b \times a_i + c
.
1 l r
: Print
\sum_{i = l}^{r - 1} a_i \bmod 998244353
.
Constraints
1 \leq N, Q \leq 500000
0 \leq a_i, c < 998244353
1 \leq b < 998244353
0 \leq l < r \leq N
All values in Input are integer.
Input
Input is given from Standard Input in the following format:
N
Q
a_0
a_1
...
a_{N - 1}
\textrm{Query}_0
\textrm{Query}_1
:
\textrm{Query}_{Q - 1}
Output
For each query of the latter type, print the answer.
Sample Input 1
5 7
1 2 3 4 5
1 0 5
0 2 4 100 101
1 0 3
0 1 3 102 103
1 2 5
0 2 5 104 105
1 0 5
Sample Output 1
15
404
41511
4317767
Problem Description: Score : 100 points
Problem Statement
You are given a binary array
A=(A_1,A_2,\cdots,A_N)
of length
N
.
Process
Q
queries of the following types. The
i
-th query is represented by three integers
T_i,L_i,R_i
.
T_i=1
: Replace the value of
A_j
with
1-A_j
for each
L_i \leq j \leq R_i
.
T_i=2
: Calculate the inversion(*) of the array
A_{L_i},A_{L_i+1},\cdots,A_{R_i}
．
Note：The inversion of the array
x_1,x_2,\cdots,x_k
is the number of the pair of integers
i,j
with
1 \leq i < j \leq k, x_i > x_j
.
Constraints
1 \leq N \leq 2 \times 10^5
0 \leq A_i \leq 1
1 \leq Q \leq 2 \times 10^5
1 \leq T_i \leq 2
1 \leq L_i \leq R_i \leq N
All values in Input are integer.
Input
Input is given from Standard Input in the following format:
N
Q
A_1
A_2
\cdots
A_N
T_1
L_1
R_1
T_2
L_2
R_2
\vdots
T_Q
L_Q
R_Q
Output
For each query with
T_i=2
, print the answer.
Sample Input 1
5 5
0 1 0 0 1
2 1 5
1 3 4
2 2 5
1 1 3
2 1 2
Sample Output 1
2
0
1
First query: Print
2
, which is the inversion of
(A_1,A_2,A_3,A_4,A_5)=(0,1,0,0,1)
.
Second query: Replace the value of
A_3
and
A_4
with
1
and
1
, respectively.
Third query: Print
0
, which is the inversion of
(A_2,A_3,A_4,A_5)=(1,1,1,1)
.
Fourth query: Replace the value of
A_1
,
A_2
and
A_4
with
1
,
0
and
0
, respectively.
Fifth query: Print
1
, which is the inversion of
(A_1,A_2)=(1,0)
.
Problem Description: Score : 100 points
Problem Statement
Takahashi is meeting up with Aoki.
They have planned to meet at a place that is
D
meters away from Takahashi's house in
T
minutes from now.
Takahashi will leave his house now and go straight to the place at a speed of
S
meters per minute.
Will he arrive in time?
Constraints
1 \leq D \leq 10000
1 \leq T \leq 10000
1 \leq S \leq 10000
All values in input are integers.
Input
Input is given from Standard Input in the following format:
D
T
S
Output
If Takahashi will reach the place in time, print
Yes
; otherwise, print
No
.
Sample Input 1
1000 15 80
Sample Output 1
Yes
It takes
12.5
minutes to go
1000
meters to the place at a speed of
80
meters per minute. They have planned to meet in
15
minutes so he will arrive in time.
Sample Input 2
2000 20 100
Sample Output 2
Yes
It takes
20
minutes to go
2000
meters to the place at a speed of
100
meters per minute. They have planned to meet in
20
minutes so he will arrive just on time.
Sample Input 3
10000 1 1
Sample Output 3
No
He will be late.
Problem Description: Score : 200 points
Problem Statement
Given are two strings
S
and
T
.
Let us change some of the characters in
S
so that
T
will be a substring of
S
.
At least how many characters do we need to change?
Here, a substring is a consecutive subsequence. For example,
xxx
is a substring of
yxxxy
, but not a substring of
xxyxx
.
Constraints
The lengths of
S
and
T
are each at least
1
and at most
1000
.
The length of
T
is at most that of
S
.
S
and
T
consist of lowercase English letters.
Input
Input is given from Standard Input in the following format:
S
T
Output
Print the minimum number of characters in
S
that need to be changed.
Sample Input 1
cabacc
abc
Sample Output 1
1
For example, changing the fourth character
a
in
S
to
c
will match the second through fourth characters in
S
to
T
.
Since
S
itself does not have
T
as its substring, this number of changes - one - is the minimum needed.
Sample Input 2
codeforces
atcoder
Sample Output 2
6
Problem Description: Score : 300 points
Problem Statement
Given are
N
integers
A_1,\ldots,A_N
.
Find the sum of
A_i \times A_j
over all pairs
(i,j)
such that
1\leq i < j \leq N
, modulo
(10^9+7)
.
Constraints
2 \leq N \leq 2\times 10^5
0 \leq A_i \leq 10^9
All values in input are integers.
Input
Input is given from Standard Input in the following format:
N
A_1
\ldots
A_N
Output
Print
\sum_{i=1}^{N-1}\sum_{j=i+1}^{N} A_i A_j
, modulo
(10^9+7)
.
Sample Input 1
3
1 2 3
Sample Output 1
11
We have
1 \times 2 + 1 \times 3 + 2 \times 3 = 11
.
Sample Input 2
4
141421356 17320508 22360679 244949
Sample Output 2
437235829
Problem Description: Score : 500 points
Problem Statement
We have
N
integers. The
i
-th number is
A_i
.
\{A_i\}
is said to be pairwise coprime when
GCD(A_i,A_j)=1
holds for every pair
(i, j)
such that
1\leq i < j \leq N
.
\{A_i\}
is said to be setwise coprime when
\{A_i\}
is not pairwise coprime but
GCD(A_1,\ldots,A_N)=1
.
Determine if
\{A_i\}
is pairwise coprime, setwise coprime, or neither.
Here,
GCD(\ldots)
denotes greatest common divisor.
Constraints
2 \leq N \leq 10^6
1 \leq A_i\leq 10^6
Input
Input is given from Standard Input in the following format:
N
A_1
\ldots
A_N
Output
If
\{A_i\}
is pairwise coprime, print
pairwise coprime
; if
\{A_i\}
is setwise coprime, print
setwise coprime
; if neither, print
not coprime
.
Sample Input 1
3
3 4 5
Sample Output 1
pairwise coprime
GCD(3,4)=GCD(3,5)=GCD(4,5)=1
, so they are pairwise coprime.
Sample Input 2
3
6 10 15
Sample Output 2
setwise coprime
Since
GCD(6,10)=2
, they are not pairwise coprime. However, since
GCD(6,10,15)=1
, they are setwise coprime.
Sample Input 3
3
6 10 16
Sample Output 3
not coprime
GCD(6,10,16)=2
, so they are neither pairwise coprime nor setwise coprime.
Problem Description: Score : 600 points
Problem Statement
There is a grid of squares with
H+1
horizontal rows and
W
vertical columns.
You will start at one of the squares in the top row and repeat moving one square right or down. However, for each integer
i
from
1
through
H
, you cannot move down from the
A_i
-th,
(A_i + 1)
-th,
\ldots
,
B_i
-th squares from the left in the
i
-th row from the top.
For each integer
k
from
1
through
H
, find the minimum number of moves needed to reach one of the squares in the
(k+1)
-th row from the top. (The starting square can be chosen individually for each case.) If, starting from any square in the top row, none of the squares in the
(k+1)
-th row can be reached, print
-1
instead.
Constraints
1 \leq H,W \leq 2\times 10^5
1 \leq A_i \leq B_i \leq W
Input
Input is given from Standard Input in the following format:
H
W
A_1
B_1
A_2
B_2
:
A_H
B_H
Output
Print
H
lines. The
i
-th line should contain the answer for the case
k=i
.
Sample Input 1
4 4
2 4
1 1
2 3
2 4
Sample Output 1
1
3
6
-1
Let
(i,j)
denote the square at the
i
-th row from the top and
j
-th column from the left.
For
k=1
, we need one move such as
(1,1)
→
(2,1)
.
For
k=2
, we need three moves such as
(1,1)
→
(2,1)
→
(2,2)
→
(3,2)
.
For
k=3
, we need six moves such as
(1,1)
→
(2,1)
→
(2,2)
→
(3,2)
→
(3,3)
→
(3,4)
→
(4,4)
.
For
k=4
, it is impossible to reach any square in the fifth row from the top.
Problem Description: Score : 200 points
Problem Statement
An integer
N
is a multiple of
9
if and only if the sum of the digits in the decimal representation of
N
is a multiple of
9
.
Determine whether
N
is a multiple of
9
.
Constraints
0 \leq N < 10^{200000}
N
is an integer.
Input
Input is given from Standard Input in the following format:
N
Output
If
N
is a multiple of
9
, print
Yes
; otherwise, print
No
.
Sample Input 1
123456789
Sample Output 1
Yes
The sum of these digits is
1+2+3+4+5+6+7+8+9=45
, which is a multiple of
9
, so
123456789
is a multiple of
9
.
Sample Input 2
0
Sample Output 2
Yes
Sample Input 3
31415926535897932384626433832795028841971693993751058209749445923078164062862089986280
Sample Output 3
No
Problem Description: Score : 300 points
Problem Statement
N
persons are standing in a row. The height of the
i
-th person from the front is
A_i
.
We want to have each person stand on a stool of some heights - at least zero - so that the following condition is satisfied for every person:
Condition: Nobody in front of the person is taller than the person. Here, the height of a person includes the stool.
Find the minimum total height of the stools needed to meet this goal.
Constraints
1 \leq N \leq 2\times 10^5
1 \leq A_i \leq 10^9
All values in input are integers.
Input
Input is given from Standard Input in the following format:
N
A_1
\ldots
A_N
Output
Print the minimum total height of the stools needed to meet the goal.
Sample Input 1
5
2 1 5 4 3
Sample Output 1
4
If the persons stand on stools of heights
0
,
1
,
0
,
1
, and
2
, respectively, their heights will be
2
,
2
,
5
,
5
, and
5
, satisfying the condition.
We cannot meet the goal with a smaller total height of the stools.
Sample Input 2
5
3 3 3 3 3
Sample Output 2
0
Giving a stool of height
0
to everyone will work.
Problem Description: Score : 500 points
Problem Statement
We have a two-dimensional grid with
H \times W
squares. There are
M
targets to destroy in this grid - the position of the
i
-th target is
\left(h_i, w_i \right)
.
Takahashi will choose one square in this grid, place a bomb there, and ignite it. The bomb will destroy all targets that are in the row or the column where the bomb is placed. It is possible to place the bomb at a square with a target.
Takahashi is trying to maximize the number of targets to destroy. Find the maximum number of targets that can be destroyed.
Constraints
All values in input are integers.
1 \leq H, W \leq 3 \times 10^5
1 \leq M \leq \min\left(H\times W, 3 \times 10^5\right)
1 \leq h_i \leq H
1 \leq w_i \leq W
\left(h_i, w_i\right) \neq \left(h_j, w_j\right) \left(i \neq j\right)
Input
Input is given from Standard Input in the following format:
H
W
M
h_1
w_1
\vdots
h_M
w_M
Output
Print the answer.
Sample Input 1
2 3 3
2 2
1 1
1 3
Sample Output 1
3
We can destroy all the targets by placing the bomb at
\left(1, 2\right)
.
Sample Input 2
3 3 4
3 3
3 1
1 1
1 2
Sample Output 2
3
Sample Input 3
5 5 10
2 5
4 3
2 3
5 5
2 2
5 4
5 3
5 1
3 5
1 4
Sample Output 3
6
Problem Description: Score : 600 points
Problem Statement
We have
3N
cards arranged in a row from left to right, where each card has an integer between
1
and
N
(inclusive) written on it. The integer written on the
i
-th card from the left is
A_i
.
You will do the following operation
N-1
times:
Rearrange the five leftmost cards in any order you like, then remove the three leftmost cards. If the integers written on those three cards are all equal, you gain
1
point.
After these
N-1
operations, if the integers written on the remaining three cards are all equal, you will gain
1
additional point.
Find the maximum number of points you can gain.
Constraints
1 \leq N \leq 2000
1 \leq A_i \leq N
Input
Input is given from Standard Input in the following format:
N
A_1
A_2
\cdots
A_{3N}
Output
Print the maximum number of points you can gain.
Sample Input 1
2
1 2 1 2 2 1
Sample Output 1
2
Let us rearrange the five leftmost cards so that the integers written on the six cards will be
2\ 2\ 2\ 1\ 1\ 1
from left to right.
Then, remove the three leftmost cards, all of which have the same integer
2
, gaining
1
point.
Now, the integers written on the remaining cards are
1\ 1\ 1
.
Since these three cards have the same integer
1
, we gain
1
more point.
In this way, we can gain
2
points - which is the maximum possible.
Sample Input 2
3
1 1 2 2 3 3 3 2 1
Sample Output 2
1
Sample Input 3
3
1 1 2 2 2 3 3 3 1
Sample Output 3
3
Problem Description: Score : 200 points
Problem Statement
We have sticks numbered
1, \cdots, N
. The length of Stick
i
(1 \leq i \leq N)
is
L_i
.
In how many ways can we choose three of the sticks with different lengths that can form a triangle?
That is, find the number of triples of integers
(i, j, k)
(1 \leq i < j < k \leq N)
that satisfy both of the following conditions:
L_i
,
L_j
, and
L_k
are all different.
There exists a triangle whose sides have lengths
L_i
,
L_j
, and
L_k
.
Constraints
1 \leq N \leq 100
1 \leq L_i \leq 10^9
All values in input are integers.
Input
Input is given from Standard Input in the following format:
N
L_1
L_2
\cdots
L_N
Output
Print the number of ways to choose three of the sticks with different lengths that can form a triangle.
Sample Input 1
5
4 4 9 7 5
Sample Output 1
5
The following five triples
(i, j, k)
satisfy the conditions:
(1, 3, 4)
,
(1, 4, 5)
,
(2, 3, 4)
,
(2, 4, 5)
, and
(3, 4, 5)
.
Sample Input 2
6
4 5 4 3 3 5
Sample Output 2
8
We have two sticks for each of the lengths
3
,
4
, and
5
. To satisfy the first condition, we have to choose one from each length.
There is a triangle whose sides have lengths
3
,
4
, and
5
, so we have
2 ^ 3 = 8
triples
(i, j, k)
that satisfy the conditions.
Sample Input 3
10
9 4 6 1 9 6 10 6 6 8
Sample Output 3
39
Sample Input 4
2
1 1
Sample Output 4
0
No triple
(i, j, k)
satisfies
1 \leq i < j < k \leq N
, so we should print
0
.
Problem Description: Score : 300 points
Problem Statement
Takahashi, who lives on the number line, is now at coordinate
X
. He will make exactly
K
moves of distance
D
in the positive or negative direction.
More specifically, in one move, he can go from coordinate
x
to
x + D
or
x - D
.
He wants to make
K
moves so that the absolute value of the coordinate of the destination will be the smallest possible.
Find the minimum possible absolute value of the coordinate of the destination.
Constraints
-10^{15} \leq X \leq 10^{15}
1 \leq K \leq 10^{15}
1 \leq D \leq 10^{15}
All values in input are integers.
Input
Input is given from Standard Input in the following format:
X
K
D
Output
Print the minimum possible absolute value of the coordinate of the destination.
Sample Input 1
6 2 4
Sample Output 1
2
Takahashi is now at coordinate
6
. It is optimal to make the following moves:
Move from coordinate
6
to (
6 - 4 =
)
2
.
Move from coordinate
2
to (
2 - 4 =
)
-2
.
Here, the absolute value of the coordinate of the destination is
2
, and we cannot make it smaller.
Sample Input 2
7 4 3
Sample Output 2
1
Takahashi is now at coordinate
7
. It is optimal to make, for example, the following moves:
Move from coordinate
7
to
4
.
Move from coordinate
4
to
7
.
Move from coordinate
7
to
4
.
Move from coordinate
4
to
1
.
Here, the absolute value of the coordinate of the destination is
1
, and we cannot make it smaller.
Sample Input 3
10 1 2
Sample Output 3
8
Sample Input 4
1000000000000000 1000000000000000 1000000000000000
Sample Output 4
1000000000000000
The answer can be enormous.
Problem Description: Score : 400 points
Problem Statement
Takahashi will play a game using a piece on an array of squares numbered
1, 2, \cdots, N
. Square
i
has an integer
C_i
written on it. Also, he is given a permutation of
1, 2, \cdots, N
:
P_1, P_2, \cdots, P_N
.
Now, he will choose one square and place the piece on that square. Then, he will make the following move some number of times between
1
and
K
(inclusive):
In one move, if the piece is now on Square
i
(1 \leq i \leq N)
, move it to Square
P_i
. Here, his score increases by
C_{P_i}
.
Help him by finding the maximum possible score at the end of the game. (The score is
0
at the beginning of the game.)
Constraints
2 \leq N \leq 5000
1 \leq K \leq 10^9
1 \leq P_i \leq N
P_i \neq i
P_1, P_2, \cdots, P_N
are all different.
-10^9 \leq C_i \leq 10^9
All values in input are integers.
Input
Input is given from Standard Input in the following format:
N
K
P_1
P_2
\cdots
P_N
C_1
C_2
\cdots
C_N
Output
Print the maximum possible score at the end of the game.
Sample Input 1
5 2
2 4 5 1 3
3 4 -10 -8 8
Sample Output 1
8
When we start at some square of our choice and make at most two moves, we have the following options:
If we start at Square
1
, making one move sends the piece to Square
2
, after which the score is
4
. Making another move sends the piece to Square
4
, after which the score is
4 + (-8) = -4
.
If we start at Square
2
, making one move sends the piece to Square
4
, after which the score is
-8
. Making another move sends the piece to Square
1
, after which the score is
-8 + 3 = -5
.
If we start at Square
3
, making one move sends the piece to Square
5
, after which the score is
8
. Making another move sends the piece to Square
3
, after which the score is
8 + (-10) = -2
.
If we start at Square
4
, making one move sends the piece to Square
1
, after which the score is
3
. Making another move sends the piece to Square
2
, after which the score is
3 + 4 = 7
.
If we start at Square
5
, making one move sends the piece to Square
3
, after which the score is
-10
. Making another move sends the piece to Square
5
, after which the score is
-10 + 8 = -2
.
The maximum score achieved is
8
.
Sample Input 2
2 3
2 1
10 -7
Sample Output 2
13
Sample Input 3
3 3
3 1 2
-1000 -2000 -3000
Sample Output 3
-1000
We have to make at least one move.
Sample Input 4
10 58
9 1 6 7 8 4 3 2 10 5
695279662 988782657 -119067776 382975538 -151885171 -177220596 -169777795 37619092 389386780 980092719
Sample Output 4
29507023469
The absolute value of the answer may be enormous.
Problem Description: Score : 500 points
Problem Statement
There are
K
items placed on a grid of squares with
R
rows and
C
columns. Let
(i, j)
denote the square at the
i
-th row (
1 \leq i \leq R
) and the
j
-th column (
1 \leq j \leq C
). The
i
-th item is at
(r_i, c_i)
and has the value
v_i
.
Takahashi will begin at
(1, 1)
, the start, and get to
(R, C)
, the goal. When he is at
(i, j)
, he can move to
(i + 1, j)
or
(i, j + 1)
(but cannot move to a non-existent square).
He can pick up items on the squares he visits, including the start and the goal, but at most three for each row. It is allowed to ignore the item on a square he visits.
Find the maximum possible sum of the values of items he picks up.
Constraints
1 \leq R, C \leq 3000
1 \leq K \leq \min(2 \times 10^5, R \times C)
1 \leq r_i \leq R
1 \leq c_i \leq C
(r_i, c_i) \neq (r_j, c_j) (i \neq j)
1 \leq v_i \leq 10^9
All values in input are integers.
Input
Input is given from Standard Input in the following format:
R
C
K
r_1
c_1
v_1
r_2
c_2
v_2
:
r_K
c_K
v_K
Output
Print the maximum possible sum of the values of items Takahashi picks up.
Sample Input 1
2 2 3
1 1 3
2 1 4
1 2 5
Sample Output 1
8
He has two ways to get to the goal:
Visit
(1, 1)
,
(1, 2)
, and
(2, 2)
, in this order. In this case, the total value of the items he can pick up is
3 + 5 = 8
.
Visit
(1, 1)
,
(2, 1)
, and
(2, 2)
, in this order. In this case, the total value of the items he can pick up is
3 + 4 = 7
.
Thus, the maximum possible sum of the values of items he picks up is
8
.
Sample Input 2
2 5 5
1 1 3
2 4 20
1 2 1
1 3 4
1 4 2
Sample Output 2
29
We have four items in the
1
-st row. The optimal choices are as follows:
Visit
(1, 1)
(1, 2)
,
(1, 3)
,
(1, 4)
,
(2, 4)
, and
(2, 5)
, in this order, and pick up all items except the one on
(1, 2)
. Then, the total value of the items he picks up will be
3 + 4 + 2 + 20 = 29
.
Sample Input 3
4 5 10
2 5 12
1 5 12
2 3 15
1 2 20
1 1 28
2 4 26
3 2 27
4 5 21
3 5 10
1 3 10
Sample Output 3
142
Problem Description: Score : 600 points
Problem Statement
We have
N
strings of lowercase English letters:
S_1, S_2, \cdots, S_N
.
Takahashi wants to make a string that is a palindrome by choosing one or more of these strings - the same string can be chosen more than once - and concatenating them in some order of his choice.
The cost of using the string
S_i
once is
C_i
, and the cost of using it multiple times is
C_i
multiplied by that number of times.
Find the minimum total cost needed to choose strings so that Takahashi can make a palindrome.
If there is no choice of strings in which he can make a palindrome, print
-1
.
Constraints
1 \leq N \leq 50
1 \leq |S_i| \leq 20
S_i
consists of lowercase English letters.
1 \leq C_i \leq 10^9
Input
Input is given from Standard Input in the following format:
N
S_1
C_1
S_2
C_2
:
S_N
C_N
Output
Print the minimum total cost needed to choose strings so that Takahashi can make a palindrome, or
-1
if there is no such choice.
Sample Input 1
3
ba 3
abc 4
cbaa 5
Sample Output 1
7
We have
ba
,
abc
, and
cbaa
.
For example, we can use
ba
once and
abc
once for a cost of
7
, then concatenate them in the order
abc
,
ba
to make a palindrome.
Also, we can use
abc
once and
cbaa
once for a cost of
9
, then concatenate them in the order
cbaa
,
abc
to make a palindrome.
We cannot make a palindrome for a cost less than
7
, so we should print
7
.
Sample Input 2
2
abcab 5
cba 3
Sample Output 2
11
We can choose
abcab
once and
cba
twice, then concatenate them in the order
abcab
,
cba
,
cba
to make a palindrome for a cost of
11
.
Sample Input 3
4
ab 5
cba 3
a 12
ab 10
Sample Output 3
8
We can choose
a
once, which is already a palindrome, but it is cheaper to concatenate
ab
and
cba
.
Sample Input 4
2
abc 1
ab 2
Sample Output 4
-1
We cannot make a palindrome, so we should print
-1
.
Problem Description: Score : 300 points
Problem Statement
You are given
N
real values
A_1, A_2, \ldots, A_N
.
Compute the number of pairs of indices
(i, j)
such that
i < j
and the product
A_i \cdot A_j
is integer.
Constraints
2 \leq N \leq 200\,000
0 < A_i < 10^4
A_i
is given with at most 9 digits after the decimal.
Input
Input is given from Standard Input in the following format.
N
A_1
A_2
\vdots
A_N
Output
Print the number of pairs with integer product
A_i \cdot A_j
(and
i < j
).
Sample Input 1
5
7.5
2.4
17.000000001
17
16.000000000
Sample Output 1
3
There are 3 pairs with integer product:
7.5 \cdot 2.4 = 18
7.5 \cdot 16 = 120
17 \cdot 16 = 272
Sample Input 2
11
0.9
1
1
1.25
2.30000
5
70
0.000000001
9999.999999999
0.999999999
1.000000001
Sample Output 2
8
Problem Description: Score : 700 points
Problem Statement
Limak can repeatedly remove one of the first two characters of a string,
    for example
abcxyx \rightarrow acxyx \rightarrow cxyx \rightarrow cyx
.
You are given
N
different strings
S_1, S_2, \ldots, S_N
.
Among
N \cdot (N-1) / 2
pairs
(S_i, S_j)
,
    in how many pairs could Limak obtain one string from the other?
Constraints
2 \leq N \leq 200\,000
S_i
consists of lowercase English letters
a
-
z
.
S_i \neq S_j
1 \leq |S_i|
|S_1| + |S_2| + \ldots + |S_N| \leq 10^6
Input
Input is given from Standard Input in the following format.
N
S_1
S_2
\vdots
S_N
Output
Print the number of unordered pairs
(S_i, S_j)
where
i \neq j
and Limak can obtain one string from the other.
Sample Input 1
3
abcxyx
cyx
abc
Sample Output 1
1
The only good pair is
(abcxyx, cyx)
.
Sample Input 2
6
b
a
abc
c
d
ab
Sample Output 2
5
There are five good pairs:
(b, abc)
,
(a, abc)
,
(abc, c)
,
(b, ab)
,
(a, ab)
.