프로그램 명: coci_razbi
제한시간: 1 초

[번역 중...] Mirko has already solved all crosswords available in daily newspapers, 미코는 신문에 있는 모든 낱말 맞추기 게임을 풀었다. and he is too intimidated by ACTA to download new ones from the Internet. Now he has asked Frane to challenge him with a programming problem. Frane has eagerly responded with a brand new task, and was kind enough not to lock the task under copyright protection, so you are allowed to attempt it too!

Four words with equal lengths can be put together in a square such that two words mark horizontal edges, while the other two mark vertical edges. Horizontal words are read left to right, and vertical ones from top to bottom. Corner letters are shared by the two neighbouring edges. The figure below shows one possible square created from words “HLAD”, “NIVA”, “HSIN”, “DEDA”.

H L A D
S     E
I     D
N I V A

Your task is, given a list of equal-length words, to compute the number of different squares that can be put together from a subset of these words. You are not allowed to repeat a word in the same square. Two squares are different if they differ in at least one character.

Mirko has already solved all crosswords available in daily newspapers, and he is too intimidated by ACTA to download new ones from the Internet. Now he has asked Frane to challenge him with a programming problem. Frane has eagerly responded with a brand new task, and was kind enough not to lock the task under copyright protection, so you are allowed to attempt it too!

Four words with equal lengths can be put together in a square such that two words mark horizontal edges, while the other two mark vertical edges. Horizontal words are read left to right, and vertical ones from top to bottom. Corner letters are shared by the two neighbouring edges. The figure below shows one possible square created from words “HLAD”, “NIVA”, “HSIN”, “DEDA”.

H L A D
S     E
I     D
N I V A

Your task is, given a list of equal-length words, to compute the number of different squares that can be put together from a subset of these words. You are not allowed to repeat a word in the same square. Two squares are different if they differ in at least one character.

입력

The first line of input contains the positive integer N (4 ≤ N ≤ 100 000), the number of words in the list. Each of the next N lines contains a single word consisting only of uppercase English letters. Each word will contain at most 10 characters. All words will be distinct and have equal length.

출력

The first and only line of output must contain the required number of distinct squares. Note: Test data will ensure that the solution fits in a 64-bit integer data type (int64 in Pascal, long long in C/C++).

입출력 예

입력

4
NIVA
HLAD
HSIN
DEDA

출력

2

입력

6
BAKA
BARA
BALC
CALC
ARHC
BLIC

출력

8

출처:coci 2011-2012 contest5 4/6
[질/답] [제출 현황] [푼 후(0)]
[ 채 점 ] [홈으로]  [뒤 로]