実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 100 点
問題文
英小文字からなる文字列 S が与えられます。 S の長さは 1 以上かつ 3 以下です。
S を繰り返して得られる文字列であって、長さが 6 のものを出力してください。
本問題の制約下で、そのような文字列はただ一つ存在することが示せます。
制約
- S は英小文字からなる長さ 1 以上 3 以下の文字列
入力
入力は以下の形式で標準入力から与えられる。
S
出力
答えとなる長さ 6 の文字列を出力せよ。
入力例 1
abc
出力例 1
abcabc
S = abc を繰り返してできる文字列として、abc 、abcabc 、abcabcabc 、abcabcabcabc などがあります。
そのうち、長さが 6 のものは abcabc です。よって、abcabc と出力します。
入力例 2
zz
出力例 2
zzzzzz
Score : 100 points
Problem Statement
You are given a string S consisting of lowercase English characters. The length of S is between 1 and 3, inclusive.
Print the string of length 6 that is a repetition of S.
It can be shown that there uniquely exists such a string under the Constraints of this problem.
Constraints
- S is a string consisting of lowercase English characters of length between 1 and 3, inclusive.
Input
Input is given from Standard Input in the following format:
S
Output
Print the answer string, which is of length 6.
Sample Input 1
abc
Sample Output 1
abcabc
These are strings that are repetitions of S = abc: abc, abcabc, abcabcabc, abcabcabcabc, and so on.
Among them, abcabc has the length of 6, so abcabc should be printed.
Sample Input 2
zz
Sample Output 2
zzzzzz
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 100 点
問題文
正整数 N が与えられるので、
N 個の 0 と N+1 個の 1 からなる、0 と 1 が交互に並んだ文字列を出力してください。
制約
- N は整数
- 1 \leq N \leq 100
入力
入力は以下の形式で標準入力から与えられる。
N
出力
答えを出力せよ。
入力例 1
4
出力例 1
101010101
4 個の 0 と 5 個の 1 からなる、0 と 1 が交互に並んだ文字列は 101010101 です。
入力例 2
1
出力例 2
101
入力例 3
10
出力例 3
101010101010101010101
Score: 100 points
Problem Statement
Given a positive integer N, print a string of N zeros and N+1 ones where 0 and 1 alternate.
Constraints
- N is an integer.
- 1 \leq N \leq 100
Input
The input is given from Standard Input in the following format:
N
Output
Print the answer.
Sample Input 1
4
Sample Output 1
101010101
A string of four zeros and five ones where 0 and 1 alternate is 101010101.
Sample Input 2
1
Sample Output 2
101
Sample Input 3
10
Sample Output 3
101010101010101010101
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 200 点
問題文
N 個のマスが左右一列に並んでおり、左から順にマス 1、マス 2、…、マス N と番号づけられています。
また、K 個のコマがあり、最初左から i 番目のコマはマス A_i に置かれています。
これらに対して、Q 回の操作を行います。
i 回目の操作では次の操作を行います。
- 左から L_i 番目のコマが一番右のマスにあるならば何も行わない。
- そうでない時、左から L_i 番目のコマがあるマスの 1 つ右のマスにコマが無いならば、左から L_i 番目のコマを 1 つ右のマスに移動させる。 1 つ右のマスにコマがあるならば、何も行わない。
Q 回の操作が終了した後の状態について、i=1,2,\ldots,K に対して左から i 番目のコマがあるマスの番号を出力してください。
制約
- 1\leq K\leq N\leq 200
- 1\leq A_1<A_2<\cdots<A_K\leq N
- 1\leq Q\leq 1000
- 1\leq L_i\leq K
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N K Q A_1 A_2 \ldots A_K L_1 L_2 \ldots L_Q
出力
K 個の整数を空白区切りで一行に出力せよ。 ここで、i 個目の整数は、 Q 回の操作が終了した後の状態について、左から i 番目のコマの番号を表す。
入力例 1
5 3 5 1 3 4 3 3 1 1 2
出力例 1
2 4 5
最初、コマはマス 1, 3, 4 にあります。これに対して以下のように操作が行われます。
- 左から 3 番目のコマはマス 4 にあります。 これは一番右のマスでなく、その 1 つ右のマスにもコマが置かれていないため、左から 3 番目のコマをマス 5 に動かします。 コマはマス 1, 3, 5 にある状態になります。
- 左から 3 番目のコマはマス 5 にあります。 これは一番右のマスなので、何も行いません。 コマはマス 1, 3, 5 にある状態のままです。
- 左から 1 番目のコマはマス 1 にあります。 これは一番右のマスでなく、その 1 つ右のマスにもコマが置かれていないため、左から 1 番目のコマをマス 2 に動かします。 コマはマス 2, 3, 5 にある状態になります。
- 左から 1 番目のコマはマス 2 にあります。 これは一番右のマスでありませんが、その 1 つ右のマス(マス 3 )にコマが置かれているため、何も行いません。 コマはマス 2, 3, 5 にある状態のままです。
- 左から 2 番目のコマはマス 3 にあります。 これは一番右のマスでなく、その右のマスにもコマが置かれていないため、左から 2 番目のコマをマス 4 に動かします。 コマはマス 2, 4, 5 にある状態になります。
よって、Q 回の操作が終わった後でコマはマス 2, 4, 5 に置かれているため、2,4,5 を空白区切りでこの順に出力します。
入力例 2
2 2 2 1 2 1 2
出力例 2
1 2
入力例 3
10 6 9 1 3 5 7 8 9 1 2 3 4 5 6 5 6 2
出力例 3
2 5 6 7 9 10
Score : 200 points
Problem Statement
There are N squares, indexed Square 1, Square 2, …, Square N, arranged in a row from left to right.
Also, there are K pieces. The i-th piece from the left is initially placed on Square A_i.
Now, we will perform Q operations against them.
The i-th operation is as follows:
- If the L_i-th piece from the left is on its rightmost square, do nothing.
- Otherwise, move the L_i-th piece from the left one square right if there is no piece on the next square on the right; if there is, do nothing.
Print the index of the square on which the i-th piece from the left is after the Q operations have ended, for each i=1,2,\ldots,K.
Constraints
- 1\leq K\leq N\leq 200
- 1\leq A_1<A_2<\cdots<A_K\leq N
- 1\leq Q\leq 1000
- 1\leq L_i\leq K
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N K Q A_1 A_2 \ldots A_K L_1 L_2 \ldots L_Q
Output
Print K integers in one line, with spaces in between. The i-th of them should be the index of the square on which the i-th piece from the left is after the Q operations have ended.
Sample Input 1
5 3 5 1 3 4 3 3 1 1 2
Sample Output 1
2 4 5
At first, the pieces are on Squares 1, 3, and 4. The operations are performed against them as follows:
- The 3-rd piece from the left is on Square 4. This is not the rightmost square, and the next square on the right does not contain a piece, so move the 3-rd piece from the left to Square 5. Now, the pieces are on Squares 1, 3, and 5.
- The 3-rd piece from the left is on Square 5. This is the rightmost square, so do nothing. The pieces are still on Squares 1, 3, and 5.
- The 1-st piece from the left is on Square 1. This is not the rightmost square, and the next square on the right does not contain a piece, so move the 1-st piece from the left to Square 2. Now, the pieces are on Squares 2, 3, and 5.
- The 1-st piece from the left is on Square 2. This is not the rightmost square, but the next square on the right (Square 3) contains a piece, so do nothing. The pieces are still on Squares 2, 3, and 5.
- The 2-nd piece from the left is on Square 3. This is not the rightmost square, and the next square on the right does not contain a piece, so move the 2-nd piece from the left to Square 4; Now, the pieces are still on Squares 2, 4, and 5.
Thus, after the Q operations have ended, the pieces are on Squares 2, 4, and 5, so 2, 4, and 5 should be printed in this order, with spaces in between.
Sample Input 2
2 2 2 1 2 1 2
Sample Output 2
1 2
Sample Input 3
10 6 9 1 3 5 7 8 9 1 2 3 4 5 6 5 6 2
Sample Output 3
2 5 6 7 9 10
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 200 点
問題文
整数 A,B が K 進法表記で与えられます。
A \times B を 10 進法表記で出力してください。
注記
K 進法表記については、Wikipedia「位取り記数法」 を参照してください。
制約
- 2 \leq K \leq 10
- 1 \leq A,B \leq 10^5
- A,B は K 進法表記で与えられる
入力
入力は以下の形式で標準入力から与えられる。
K A B
出力
答えを出力せよ。
入力例 1
2 1011 10100
出力例 1
220
2 進法表記の 1011 を 、10 進法表記すると 11 です。
2 進法表記の 10100 を、 10 進法表記すると 20 です。
11 \times 20 = 220 なので 220 を出力します。
入力例 2
7 123 456
出力例 2
15642
7 進法表記の 123 を 、10 進法表記すると 66 です。
7 進法表記の 456 を、 10 進法表記すると 237 です。
66 \times 237 = 15642 なので 15642 を出力します。
Score : 200 points
Problem Statement
You are given integers A and B, in base K.
Print A \times B in decimal.
Notes
For base-K representation, see Wikipedia's article on Positional notation.
Constraints
- 2 \leq K \leq 10
- 1 \leq A,B \leq 10^5
- A and B are in base-K representation.
Input
Input is given from Standard Input in the following format:
K A B
Output
Print the answer.
Sample Input 1
2 1011 10100
Sample Output 1
220
1011 in base 2 corresponds to 11 in base 10.
10100 in base 2 corresponds to 20 in base 10.
We have 11 \times 20 = 220, so print 220.
Sample Input 2
7 123 456
Sample Output 2
15642
123 in base 7 corresponds to 66 in base 10.
456 in base 7 corresponds to 237 in base 10.
We have 66 \times 237 = 15642, so print 15642.
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 350 点
問題文
N 棟のビルが等間隔に一列に並んでいます。手前から i 番目のビルの高さは H_i です。
あなたは次の条件をともに満たすようにいくつかのビルを選んで電飾で飾ろうとしています。
- 選んだビルたちは高さが等しい
- 選んだビルたちは等間隔に並んでいる
最大でいくつのビルを選ぶことができますか? なお、ちょうど 1 つのビルを選んだときは条件を満たすとみなします。
制約
- 1 \leq N \leq 3000
- 1 \leq H_i \leq 3000
- 入力は全て整数である
入力
入力は以下の形式で標準入力から与えられる。
N H_1 \ldots H_N
出力
答えを出力せよ。
入力例 1
8 5 7 5 7 7 5 7 7
出力例 1
3
手前から 2,5,8 番目のビルを選ぶと条件を満たします。
入力例 2
10 100 200 300 400 500 600 700 800 900 1000
出力例 2
1
1つのビルを選んだときは条件を満たすとみなします。
入力例 3
32 3 1 4 1 5 9 2 6 5 3 5 8 9 7 9 3 2 3 8 4 6 2 6 4 3 3 8 3 2 7 9 5
出力例 3
3
Score : 350 points
Problem Statement
There are N buildings arranged in a line at equal intervals. The height of the i-th building from the front is H_i.
You want to decorate some of these buildings with illuminations so that both of the following conditions are satisfied:
- The chosen buildings all have the same height.
- The chosen buildings are arranged at equal intervals.
What is the maximum number of buildings you can choose? If you choose exactly one building, it is considered to satisfy the conditions.
Constraints
- 1 \leq N \leq 3000
- 1 \leq H_i \leq 3000
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N H_1 \ldots H_N
Output
Print the answer.
Sample Input 1
8 5 7 5 7 7 5 7 7
Sample Output 1
3
Choosing the 2nd, 5th, and 8th buildings from the front satisfies the conditions.
Sample Input 2
10 100 200 300 400 500 600 700 800 900 1000
Sample Output 2
1
Choosing just one building is considered to satisfy the conditions.
Sample Input 3
32 3 1 4 1 5 9 2 6 5 3 5 8 9 7 9 3 2 3 8 4 6 2 6 4 3 3 8 3 2 7 9 5
Sample Output 3
3
実行時間制限: 3 sec / メモリ制限: 1024 MiB
配点 : 300 点
問題文
文字列 T が次の条件を満たすとき、T を良い括弧列と呼びます。
-
次の操作を 0 回以上繰り返すことで T を空文字列にすることができる。
- T に(連続な)部分文字列として含まれる
()を選び、これを取り除く。
- T に(連続な)部分文字列として含まれる
例えば () や (()()), および空文字列は良い括弧列ですが、)()( や ))) は良い括弧列ではありません。
文字列 S があります。S ははじめ空文字列です。
以下で説明されるクエリを与えられる順に Q 個処理してください。そして、各クエリの直後に S が良い括弧列であるかを判定してください。
クエリは次の 2 種類です。
1 c: 文字 c が与えられる。c は(または)である。c を S の末尾に追加する。2: S の末尾の文字を削除する。この時、S は空文字列でないことが保証される。
制約
- 1 \leq Q \leq 8 \times 10^5
- 1 種類目のクエリの c は
(または) - 2 種類目のクエリを与えられた時点で S は空でないことが保証される
- Q は整数
入力
入力は以下の形式で標準入力から与えられる。ここで \mathrm{query}_i は i 番目のクエリを意味する。
Q
\mathrm{query}_1
\mathrm{query}_2
\vdots
\mathrm{query}_Q
各クエリは以下の 2 種類のいずれかの形式で与えられる。
1 c
2
出力
Q 行出力せよ。i 行目には、i 番目のクエリを処理した直後の文字列 S が良い括弧列である場合は Yes を、そうでない場合は No を出力せよ。
入力例 1
8 1 ( 2 1 ( 1 ) 2 1 ( 1 ) 1 )
出力例 1
No Yes No Yes No No No Yes
1 番目のクエリを処理した直後の S は ( で、これは良い括弧列ではありません。
2 番目のクエリを処理した直後の S は空文字列で、これは良い括弧列です。
3 番目のクエリを処理した直後の S は ( で、これは良い括弧列ではありません。
4 番目のクエリを処理した直後の S は () で、これは良い括弧列です。
5 番目のクエリを処理した直後の S は ( で、これは良い括弧列ではありません。
6 番目のクエリを処理した直後の S は (( で、これは良い括弧列ではありません。
7 番目のクエリを処理した直後の S は (() で、これは良い括弧列ではありません。
8 番目のクエリを処理した直後の S は (()) で、これは良い括弧列です。
Score : 300 points
Problem Statement
A string T is called a good bracket sequence if and only if it satisfies the following condition:
-
T can be made into an empty string by repeating the following operation zero or more times:
- Choose
()contained in T as a (contiguous) substring and remove it.
- Choose
For example, (), (()()), and the empty string are good bracket sequences, but )()( and ))) are not good bracket sequences.
There is a string S. Initially, S is an empty string.
Process Q queries in the order they are given. After each query, determine whether S is a good bracket sequence.
There are two types of queries:
1 c: A character c is given. c is either(or). Append c to the end of S.2: Remove the last character of S. It is guaranteed that S is not an empty string at this time.
Constraints
- 1 \leq Q \leq 8 \times 10^5
- c in queries of the first type is
(or). - It is guaranteed that S is not empty when a query of the second type is given.
- Q is an integer.
Input
The input is given from Standard Input in the following format, where \mathrm{query}_i denotes the i-th query.
Q
\mathrm{query}_1
\mathrm{query}_2
\vdots
\mathrm{query}_Q
Each query is given in one of the following two formats:
1 c
2
Output
Output Q lines. The i-th line should contain Yes if the string S immediately after processing the i-th query is a good bracket sequence, and No otherwise.
Sample Input 1
8 1 ( 2 1 ( 1 ) 2 1 ( 1 ) 1 )
Sample Output 1
No Yes No Yes No No No Yes
S immediately after processing the 1st query is (, which is not a good bracket sequence.
S immediately after processing the 2nd query is an empty string, which is a good bracket sequence.
S immediately after processing the 3rd query is (, which is not a good bracket sequence.
S immediately after processing the 4th query is (), which is a good bracket sequence.
S immediately after processing the 5th query is (, which is not a good bracket sequence.
S immediately after processing the 6th query is ((, which is not a good bracket sequence.
S immediately after processing the 7th query is ((), which is not a good bracket sequence.
S immediately after processing the 8th query is (()), which is a good bracket sequence.
実行時間制限: 3 sec / メモリ制限: 1024 MiB
配点 : 400 点
問題文
N 以下の正整数のうち、 a<b<c なる 素数 a,b,c を用いて a^2 \times b \times c^2 と表せるものはいくつありますか?
制約
- N は 300 \le N \le 10^{12} を満たす整数
入力
入力は以下の形式で標準入力から与えられる。
N
出力
答えを整数として出力せよ。
入力例 1
1000
出力例 1
3
1000 以下で条件を満たす整数は以下の 3 つです。
- 300 = 2^2 \times 3 \times 5^2
- 588 = 2^2 \times 3 \times 7^2
- 980 = 2^2 \times 5 \times 7^2
入力例 2
1000000000000
出力例 2
2817785
Score : 400 points
Problem Statement
How many positive integers no greater than N can be represented as a^2 \times b \times c^2 with three primes a,b, and c such that a<b<c?
Constraints
- N is an integer satisfying 300 \le N \le 10^{12}.
Input
The input is given from Standard Input in the following format:
N
Output
Print the answer as an integer.
Sample Input 1
1000
Sample Output 1
3
The conforming integers no greater than 1000 are the following three.
- 300 = 2^2 \times 3 \times 5^2
- 588 = 2^2 \times 3 \times 7^2
- 980 = 2^2 \times 5 \times 7^2
Sample Input 2
1000000000000
Sample Output 2
2817785
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 450 点
問題文
N 個のマスが左右一列に並んでいます。
左から i (1\leq i\leq N) 番目のマスをマス i と呼びます。
最初、すべてのマスは白く塗られています。
Q 個のクエリが与えられるので、順に処理してください。
i (1\leq i\leq Q) 個目のクエリは次のとおりです。
2 つの整数 (L_i,R_i) (1\leq L_i\leq R_i\leq N) が与えられる。
マス L_i, L_i+1, \ldots, R_i をすべて黒く塗る。
このとき、元々白く塗られていたマスは新しく黒く塗られ、元々黒く塗られていたマスはそのままとなる。
その後、(N 個のマスのうち)白く 塗られているマスの個数を求める。
制約
- 1\leq N\leq 10^9
- 1\leq Q\leq 2\times 10^5
- 1\leq L_i\leq R_i\leq N
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N Q L_1 R_1 L_2 R_2 \vdots L_Q R_Q
出力
Q 行出力せよ。
i 行目 (1\leq i\leq Q) には、i 個目のクエリに対する答えを出力せよ。
入力例 1
10 5 3 5 8 9 5 8 2 9 6 6
出力例 1
7 5 3 2 2
最初、10 個のマスが左右一列に並んでいます。
- 1 個目のクエリではマス 3,4,5 を黒く塗ります。操作後、白く塗られているのはマス 1,2,6,7,8,9,10 の 7 マスです。
- 2 個目のクエリではマス 8,9 を黒く塗ります。操作後、白く塗られているのはマス 1,2,6,7,10 の 5 マスです。
- 3 個目のクエリではマス 5,6,7,8 を黒く塗ります。操作後、白く塗られているのはマス 1,2,10 の 3 マスです。
- 4 個目のクエリではマス 2,3,\ldots,9 を黒く塗ります。操作後、白く塗られているのはマス 1,10 の 2 マスです。
- 5 個目のクエリではマス 6 を黒く塗ります。操作後、白く塗られているのはマス 1,10 の 2 マスです。
よって、7,5,3,2,2 をこの順に各行に出力します。
入力例 2
1000000000 1 1 500000000
出力例 2
500000000
Score : 450 points
Problem Statement
There are N cells arranged in a row from left to right.
The i-th cell from the left (1\leq i\leq N) is called cell i.
Initially, all cells are painted white.
Process Q queries in order.
The i-th query (1\leq i\leq Q) is as follows:
Two integers (L_i,R_i) (1\leq L_i\leq R_i\leq N) are given.
Paint all cells L_i, L_i+1, \ldots, R_i black.
Here, cells that were painted white are now painted black, and cells that were painted black remain as is.
After that, find the number of cells (among the N cells) that are painted white.
Constraints
- 1\leq N\leq 10^9
- 1\leq Q\leq 2\times 10^5
- 1\leq L_i\leq R_i\leq N
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N Q L_1 R_1 L_2 R_2 \vdots L_Q R_Q
Output
Output Q lines.
The i-th line (1\leq i\leq Q) should contain the answer to the i-th query.
Sample Input 1
10 5 3 5 8 9 5 8 2 9 6 6
Sample Output 1
7 5 3 2 2
Initially, 10 cells are arranged in a row from left to right.
- The first query paints cells 3,4,5 black. After the operation, the cells painted white are cells 1,2,6,7,8,9,10, which is 7 cells.
- The second query paints cells 8,9 black. After the operation, the cells painted white are 1,2,6,7,10, which is 5 cells.
- The third query paints cells 5,6,7,8 black. After the operation, the cells painted white are 1,2,10, which is 3 cells.
- The fourth query paints cells 2,3,\ldots,9 black. After the operation, the cells painted white are 1,10, which is 2 cells.
- The fifth query paints cell 6 black. After the operation, the cells painted white are cells 1,10, which is 2 cells.
Thus, output 7,5,3,2,2 in this order on each line.
Sample Input 2
1000000000 1 1 500000000
Sample Output 2
500000000
実行時間制限: 4 sec / メモリ制限: 1024 MiB
配点 : 525 点
問題文
A \cap B = \emptyset を満たす 2 つの整数の集合 A, B に対して、f(A,B) を以下のように定義します。
- A \cup B に含まれる要素を昇順に並べた数列を C=(C_1,C_2,\dots,C_{|A|+|B|}) とする。
- A=\lbrace C_{k_1},C_{k_2},\dots,C_{k_{|A|}}\rbrace となるような k_1,k_2,\dots,k_{|A|} をとる。 このとき、\displaystyle f(A,B)=\sum_{i=1}^{|A|} k_i とする。
例えば、A=\lbrace 1,3\rbrace,B=\lbrace 2,8\rbrace のとき、C=(1,2,3,8) より A=\lbrace C_1,C_3\rbrace なので、f(A,B)=1+3=4 です。
それぞれが M 個の要素からなる N 個の整数の集合 S_1,S_2\dots,S_N があり、各 i\ (1 \leq i \leq N) について S_i = \lbrace A_{i,1},A_{i,2},\dots,A_{i,M}\rbrace です。 ただし、S_i \cap S_j = \emptyset\ (i \neq j) が保証されます。
\displaystyle \sum_{1\leq i<j \leq N} f(S_i, S_j) を求めてください。
制約
- 1\leq N \leq 10^4
- 1\leq M \leq 10^2
- 1\leq A_{i,j} \leq 10^9
- i_1 \neq i_2 または j_1 \neq j_2 ならば A_{i_1,j_1} \neq A_{i_2,j_2}
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N M
A_{1,1} A_{1,2} \dots A_{1,M}
\vdots
A_{N,1} A_{N,2} \dots A_{N,M}
出力
答えを整数として出力せよ。
入力例 1
3 2 1 3 2 8 4 6
出力例 1
12
S_1,S_2 はそれぞれ問題文中で例示した A,B と一致し、f(S_1,S_2)=1+3=4 です。 f(S_1,S_3)=1+2=3,f(S_2,S_3)=1+4=5 であるため、4+3+5=12 が答えです。
入力例 2
1 1 306
出力例 2
0
入力例 3
4 4 155374934 164163676 576823355 954291757 797829355 404011431 353195922 138996221 191890310 782177068 818008580 384836991 160449218 545531545 840594328 501899080
出力例 3
102
Score : 525 points
Problem Statement
For two sets of integers, A and B, such that A \cap B = \emptyset, we define f(A,B) as follows.
- Let C=(C_1,C_2,\dots,C_{|A|+|B|}) be a sequence consisting of the elements of A \cup B, sorted in ascending order.
- Take k_1,k_2,\dots,k_{|A|} such that A=\lbrace C_{k_1},C_{k_2},\dots,C_{k_{|A|}}\rbrace. Then, let \displaystyle f(A,B)=\sum_{i=1}^{|A|} k_i.
For example, if A=\lbrace 1,3\rbrace and B=\lbrace 2,8\rbrace, then C=(1,2,3,8), so A=\lbrace C_1,C_3\rbrace; thus, f(A,B)=1+3=4.
We have N sets of integers, S_1,S_2\dots,S_N, each of which has M elements. For each i\ (1 \leq i \leq N), S_i = \lbrace A_{i,1},A_{i,2},\dots,A_{i,M}\rbrace. Here, it is guaranteed that S_i \cap S_j = \emptyset\ (i \neq j).
Find \displaystyle \sum_{1\leq i<j \leq N} f(S_i, S_j).
Constraints
- 1\leq N \leq 10^4
- 1\leq M \leq 10^2
- 1\leq A_{i,j} \leq 10^9
- If i_1 \neq i_2 or j_1 \neq j_2, then A_{i_1,j_1} \neq A_{i_2,j_2}.
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N M
A_{1,1} A_{1,2} \dots A_{1,M}
\vdots
A_{N,1} A_{N,2} \dots A_{N,M}
Output
Print the answer as an integer.
Sample Input 1
3 2 1 3 2 8 4 6
Sample Output 1
12
S_1 and S_2 respectively coincide with A and B exemplified in the problem statement, and f(S_1,S_2)=1+3=4. Since f(S_1,S_3)=1+2=3 and f(S_2,S_3)=1+4=5, the answer is 4+3+5=12.
Sample Input 2
1 1 306
Sample Output 2
0
Sample Input 3
4 4 155374934 164163676 576823355 954291757 797829355 404011431 353195922 138996221 191890310 782177068 818008580 384836991 160449218 545531545 840594328 501899080
Sample Output 3
102