성실한 학생

성실한 학생 빌리는 그래프 이론을 공부하고 있다. 빌리는 위 그림에 나온 그래프를 만드는 프로그램을 작성해야 한다.

정점에는 정수 키 $0, 1, \dots, N-1$ 이 붙어 있다 ($N \le 10000$). 그래프에는 두 종류의 방향 간선이 있다. 그림에서 F로 표시된 전방(forward) 간선과 B로 표시된 후방(backward) 간선이다. 정점은 두 개씩 한 행을 이루며, 행 $r$ 에는 키 $2r$(왼쪽)과 $2r+1$(오른쪽)이 있다. 전방 간선은 한 정점에서 바로 아래 행의 반대쪽 열로 향한다. 즉 $2r$ 에서 $2r+3$ 으로, $2r+1$ 에서 $2r+2$ 로 간다. 후방 간선은 한 정점에서 바로 위 행의 같은 열로, 즉 정점 $u$ 에서 $u-2$ 로 곧장 올라간다. 맨 위 정점 $0$ 과 $1$ 에는 후방 간선이 없다.

프로그램은 정점 $0, 1, 2, 3$ 을 담은 초기 그래프에서 시작하여, 명령의 나열에 따라 그래프를 계속 만들어 간다. 각 명령은 다음 형태이다.

index0 string_of_characters index1

여기서 index0 과 index1 은 정점의 키이고, string_of_characters 는 오른쪽에서 왼쪽으로 실행되는 동작들의 나열이다. 각 동작은 다음 문자 중 하나이다.

< 와 = 동작은 나타날 경우 동작 문자열의 가장 왼쪽에만 올 수 있으며, 따라서 가장 마지막에 실행된다.

여기서 v 는 정점 키로 색인되는 노드 배열이다. 가장 오른쪽(가장 먼저 실행되는) 동작의 현재 노드는 v[index1] 이며, f 나 b 는 그 왼쪽 동작들을 위한 현재 노드를 갱신한다. 노드는 오직 < 동작으로만 v 에 저장된다. 처음에 배열은 v[0] = 0, v[1] = 1, v[2] = 2, v[3] = 3 을 담고 있다.

입력은 명령의 나열을 담은 텍스트 파일이다. 토큰 사이에는 공백 문자(스페이스, 탭, 줄바꿈)가 자유롭게 나타날 수 있다. 입력은 파일의 끝에서 종료된다.

각 k 및 = 동작은 그 결과를 한 줄에, 줄의 처음부터 출력하며 사이에 빈 줄을 두지 않는다. 결과는 동작이 실행되는 순서대로 출력한다.