문제 난이도 측정하기

당신의 팀이 운 좋게 ACM-ICPC 월드 파이널에 진출했다면, 마주하게 될 상황 중 하나는 바로 월드 파이널 대회 그 자체이다.

각 대회가 시작될 때, 모든 팀은 서로 다른 두 가지 목표를 이루려고 한다.

1. 주어진 문제들 중에서 가장 쉬운 문제를 찾는다.
2. 그 문제를 가능한 한 빠르게 푼다.

모든 팀의 실력을 자세히 평가하기 위해, 우리는 이 두 목표를 각각 따로 시험하려고 한다. 이 문제는 첫 번째 목표, 즉 가장 쉬운 문제를 찾는 능력을 다룬다. (두 번째 목표인 실제로 푸는 능력은 다른 문제에서 다룬다.)

문제 난이도를 비교할 때 가장 까다로운 점은 사람마다 의견이 다를 수 있다는 것이다. 모두를 만족시키려면 어느 정도의 합의가 필요하므로, 먼저 의견이 일치하는 문제들부터 찾는 것으로 시작한다.

당신의 팀에게 ICPC 문제들의 집합이 주어진다. 각 팀원은 모든 문제를 예상 난이도 순으로 정렬한다. 그런 다음, 세 팀원의 정렬 모두에서 상대적인 순서가 동일한 문제 쌍을 모두 찾고자 한다.

입력은 여러 개의 태스크로 이루어진다. 각 태스크는 고려할 문제의 개수인 정수 $N$ ($2 \le N \le 150,000$) 하나가 적힌 줄로 시작한다.

그 뒤에 세 개의 블록이 이어지며, 각 블록은 한 팀원의 의견을 나타낸다(각 팀은 세 명으로 이루어진다). 각 블록은 문제를 나타내는 수 $1 \ldots N$ 의 임의의 순열을 담는다. 순열이므로 각 수는 블록마다 정확히 한 번씩 나타난다.

각 블록은 새로운 줄에서 시작한다. 표현상의 이유로 한 블록 안의 수들은 여러 줄에 나뉘어 적힐 수 있으며, 한 줄에 여러 수가 있을 때에는 적어도 하나의 공백으로 구분된다. 블록의 앞뒤에 빈 줄이 나타날 수도 있다.

마지막 태스크 다음에는 $0$ 하나가 적힌 줄이 온다.

각 태스크마다, 세 순열 모두에서 상호 순서가 동일한 문제 쌍의 개수를 정수 하나로 한 줄에 출력한다.

결과는 $N \cdot (N-1)/2$ 까지 커질 수 있으므로 $2^{32}$ 을 넘을 수 있음에 유의하라.