존은 소들에게 글자를 가르치기 위해 어린이들이 사용하는 단어 판 \(N\)개를 준비했다. 각 단어 판의 양쪽 면에는 단어 하나와 그 단어를 나타내는 그림이 있다. 예를 들어 한쪽 면에는 고양이 그림과 cat이 있고, 반대쪽 면에는 개 그림과 dog가 있을 수 있다.

단어 판들을 바닥에 놓으면 각 단어 판에서 한쪽 면만 위를 향하므로 총 \(N\)개의 단어가 보인다. 일부 단어 판을 뒤집으면 다른 단어들이 보이게 할 수 있다.

존은 소들이 철자를 연습할 수 있도록 알파벳 소문자 하나가 새겨진 나무 블록들을 만들려고 한다. 어떤 단어 판들을 뒤집더라도 위를 향한 \(N\)개의 단어를 모두 블록으로 만들 수 있도록 각 알파벳 블록을 충분히 준비해야 한다. 하나의 블록은 한 단어의 한 글자를 만드는 데에만 사용할 수 있다.

예를 들어 \(N=3\)이고 위를 향한 단어가 box, cat, car라면 b, o, x, t, r 블록은 각각 하나 이상 필요하고, c와 a 블록은 각각 두 개 이상 필요하다.

각 단어 판의 양쪽 면에 적힌 단어가 주어질 때, 어느 면들이 위를 향하더라도 모든 단어를 만들기 위해 필요한 각 알파벳 블록의 최소 개수를 구하여라.

입력

첫째 줄에 단어 판의 수 \(N\)이 주어진다.

다음 \(N\)개의 줄에 각 단어 판의 양쪽 면에 적힌 두 단어가 공백으로 구분되어 주어진다. 각 단어는 알파벳 소문자로만 이루어져 있다.

출력

총 \(26\)개의 줄을 출력한다.

첫째 줄에는 a 블록의 최소 개수, 둘째 줄에는 b 블록의 최소 개수를 출력한다. 같은 방법으로 알파벳 순서대로 각 문자의 블록 개수를 한 줄에 하나씩 출력한다.

제한 사항

• \(1 \le N \le 100\)
• 각 단어의 길이는 \(1\) 이상 \(10\) 이하이다.

예제 입력 1

3
fox box
dog cat
car bus

예제 출력 1

2
2
2
1
0
1
1
0
0
0
0
0
0
0
2
0
0
1
1
1
1
0
0
1
0
0

예제 설명 1

단어 판이 \(3\)개이므로 위를 향하는 단어의 조합은 다음과 같이 \(2^3=8\)가지이다.

fox dog car
fox dog bus
fox cat car
fox cat bus
box dog car
box dog bus
box cat car
box cat bus

이 여덟 가지 중 어느 조합이 보이더라도 세 단어를 모두 만들 수 있을 만큼 각 알파벳 블록을 준비해야 한다.

출처

USACO 2016 December Contest, Bronze, Problem 2. Block Game