기적의 도시 아미다

기적의 도시 아미다(Amida, the City of Miracle)의 시장은 다른 도시처럼 선거로 뽑지 않는다. 오랜 정권 다툼과 천재지변으로 지쳐 버린 이 도시는 모든 후보를 공평하게 뽑으면서 행운의 별 아래 태어난 사람을 시장으로 만들기 위해, 모든 후보의 운명을 제비에 맡기기로 했다. 훗날 아미다쿠지라고 불리게 되는 제비다.

선거는 다음과 같이 치러진다. 후보자 수와 같은 수의 긴 세로선을 긋고, 그 위에 여러 개의 가로선을 긋는다. 가로선은 서로 이웃한 세로선의 중간 지점끼리 연결하도록 긋는다. 세로선 중 하나의 아래에는 "당선"이라고 적혀 있다. 어느 세로선이 당선인지는 후보자들이 알 수 없도록 숨긴다. 각 후보는 세로선을 하나씩 고른다. 모든 후보가 선택을 마치면, 각 후보는 선을 위에서 아래로 따라간다. 이동 중에 가로선을 만나면 가로선이 연결된 반대쪽 세로선으로 옮겨 간 뒤 다시 아래로 따라간다. 세로선의 맨 아래에 도착했을 때 그곳에 "당선"이라고 적혀 있던 사람이 당선되어 다음 시장이 된다.

이 방법은 잘 통했다. 운 좋은 시장 아래에서 다툼도 재해도 적은 평화로운 시대가 이어졌다. 그러나 최근 인구 증가 때문에 이 방식에 한계가 드러났다. 후보자가 늘어 아미다쿠지가 대규모가 되면서 손으로 집계하기에는 시간이 너무 오래 걸리게 된 것이다. 그래서 시에서는 시청의 프로그래머인 당신에게 아미다쿠지의 전산화를 의뢰했다.

당신의 일은 아미다쿠지의 구조와 선택된 세로선의 위치가 주어졌을 때, 최종적으로 어느 세로선에 도착하는지 구하는 프로그램을 작성하는 것이다.

다음 그림은 샘플로 주어진 입력과 출력의 내용을 나타낸 것이다.

입력은 여러 데이터 세트로 이루어진다. 하나의 데이터 세트는 다음과 같이 주어진다.

n m a
가로선1
가로선2
가로선3
...
가로선m

n, m, a는 각각 2 ≤ n ≤ 100, 0 ≤ m ≤ 1000, 1 ≤ a ≤ n을 만족하는 정수이고, 각각 세로선의 개수, 가로선의 개수, 확인할 세로선의 번호를 나타낸다.

가로선의 데이터는 다음과 같이 주어진다.

h p q

h, p, q는 각각 1 ≤ h ≤ 1000, 1 ≤ p < q ≤ n을 만족하는 정수이고, h는 그 가로선의 높이, p, q는 그 가로선에 연결된 두 세로선의 번호를 나타낸다.

한 세로선의 같은 높이에 서로 다른 가로선이 둘 이상 붙는 경우는 없다.

입력의 끝에는 공백으로 구분된 세 개의 0만으로 이루어진 줄이 있다.

각 데이터 세트마다 한 줄씩, 세로선 a의 위쪽 끝에서 따라갔을 때 아래쪽 끝에서의 세로선 번호를 출력하라.