15987번 - 팀 빌딩 서브태스크

소프트콘 대회에 참가한 현욱은 파죽지세로 8개의 문제를 풀고 마지막 한 문제만을 남겨두게 되었다. 하지만 이상하게 현욱은 이 문제가 잘 풀리질 않았고, 한참 고민하는 사이 다른 사람들이 서서히 현욱의 점수를 따라오기 시작했다. 빨리 대회 우승을 확정짓고 게임하러 가고 싶다는 조바심에 현욱은 결국 부정 행위를 마음 먹고 말았다.

그리고 현욱은 언제나 자신을 도와주는 좋은 친구인 당신에게 마지막 문제를 대신 풀어달라고 부탁했다. 현욱이 보내온 마지막 문제의 요약은 다음과 같다. 현욱을 도와 대신 문제를 풀어주자!

*

어떤 회사에 총 N명의 사람이 있다. 각 사원에게는 입사한 순서대로 1~N번까지 번호가 붙어있다. 이때 이 사원들을 적절하게 팀에 배치하기 위해 다음 세 가지 명령을 사용한다.

- 1 X Y : X가 속한 팀과 Y가 속한 팀을 한 팀으로 합친다. (1 ≤ X, Y ≤ N)

- 2 X K : X가 속한 팀을 사원 번호를 P로 나눈 나머지가 K인 팀과 그렇지 않은 팀으로 나눈다. (1 ≤ X ≤ N, 0 ≤ K < P)

- 3 X : X가 속한 팀의 총 인원수를 출력한다.(1 ≤ X ≤ N)

Q개의 명령이 주어졌을 때 주어진 명령의 수행 결과를 출력하는 프로그램을 작성해보자.

첫째 줄에 정수 N,P,Q가 주어진다.

둘째 줄부터 Q줄에 걸쳐 명령이 주어진다.

각각의 3번 명령에 대해 그 결과를 한 줄에 하나씩 명령이 주어진 순서대로 출력한다. 3번 명령은 반드시 한 번 이상 주어진다.

• 1 ≤ N, Q ≤ 10⁵
• 2 ≤ P ≤ 30

• N ≤ 3000, Q ≤ 20000
• P = 2

• P = 2

• 추가 제한 없음