식당 메뉴

여러 명의 학생이 식사를 하려고 학교 식당을 향해 달려가고 있다. 식당에 도착한 학생은 입구에 줄을 서서 기다린다. 먼저 도착한 학생이 나중에 도착한 학생보다 줄의 앞쪽에 선다. 식사는 1인분씩 준비된다. 식사 1인분이 준비되면 줄 맨 앞의 학생 1명이 식당에 들어가 식사를 시작한다. 식사를 시작한 학생은 항상 식사를 마친다.

학교 식당에서는 메뉴 두 가지를 제공하며, 각 학생은 두 메뉴 중 좋아하는 메뉴를 이미 정해 두었다. $n$개의 식당 정보가 저장된 $S$가 주어진다. $S$의 첫 번째 정보부터 $n$번째 정보까지 순서대로 처리했을 때, 좋아하는 메뉴를 먹은 학생 목록 $A$, 좋아하지 않는 메뉴를 먹은 학생 목록 $B$, 식당에 도착했지만 식사를 하지 못한 학생 목록 $C$를 출력하라.

$S$에 저장된 정보는 다음 두 유형 중 하나이다.

• 유형 1: 1 a b. 학생 번호가 양의 정수 $a$이고 좋아하는 메뉴 번호가 양의 정수 $b$인 학생 1명이 식당에 도착하여 줄 맨 뒤에 선다.
• 유형 2: 2 b. 메뉴 번호가 양의 정수 $b$인 식사 1인분이 준비된다. 줄 맨 앞의 학생 1명이 식사를 시작한다.

식사 1인분이 준비될 때는 줄에 기다리는 학생이 항상 있다. 줄에서 기다리기만 하고 식사가 준비되지 않은 학생은 식사를 하지 못한다.

첫 번째 줄에 $n$이 주어진다.

두 번째 줄부터 $n$개의 줄에 걸쳐 한 줄에 정보가 하나씩 주어진다. 각 정보는 유형 1 또는 유형 2이다.

첫 번째 줄에 목록 $A$의 학생 번호를 오름차순으로 빈칸을 사이에 두고 출력한다.

두 번째 줄에 목록 $B$의 학생 번호를 오름차순으로 빈칸을 사이에 두고 출력한다.

세 번째 줄에 목록 $C$의 학생 번호를 오름차순으로 빈칸을 사이에 두고 출력한다.

목록에 학생이 없으면 학생 번호 대신 None을 출력한다.

• $1 \le n \le 500{,}000$
• $S$에는 유형 1과 유형 2만 저장되어 있다.
• $1 \le a \le n$이며, 모든 양의 정수 $a$의 값은 서로 다르다.
• $b$는 1 또는 2이다.