전설의 JBNU

전설의 프로그래머 윤준하는 자신만의 데이터베이스 시스템 JBNU(Jeong Bo Neoh Um)를 만들었다.

JBNU에 저장되는 데이터 하나는 데이터를 찾는 데 쓰는 Key와 데이터의 내용인 Value 한 쌍이다. Key를 알아야 원하는 데이터를 꺼낼 수 있다.

준하는 건망증이 심해 Key를 자꾸 잊었다. 그래서 JBNU를 고쳐, 저장되지 않은 Key를 입력해도 그 Key에 가장 가까운 Key를 찾아 주는 기능을 넣었다.

Key와 Value는 모두 정수다. 가장 가까운 Key는 입력한 Key와의 차이가 가장 작은 Key를 말한다. 정보의 정확성을 위해, 차이가 $K$보다 큰 Key는 후보로 인정하지 않는다.

프로젝트 베끼기의 달인 승균이는 데이터베이스 수업에서 JBNU를 모방하기로 했다. 그런데 준하는 전설이라 그가 만든 프로그램은 구할 방법이 없었고, 승균이는 같은 조원인 당신에게 구현을 맡기려 한다.

JBNU의 초기 데이터가 주어질 때, 데이터 추가와 수정, 검색을 지원하는 프로그램을 작성하자.

첫 줄에 초기 데이터의 개수 $N(1 \le N \le 100{,}000)$, 명령의 횟수 $M(1 \le M \le 100{,}000)$, 가장 가까운 Key까지의 거리 제한 $K(1 \le K \le 10{,}000)$가 주어진다.

둘째 줄부터 $N$개의 줄에는 초기 데이터의 Key와 Value가 한 줄에 하나씩 주어진다. 모든 Key와 Value는 $1{,}000{,}000{,}000$ 이하의 음이 아닌 정수다. Key가 같은 데이터는 없다.

다음 $M$개의 줄에는 아래 세 가지 중 하나의 명령이 주어진다.

• 1 Key Value: 주어진 Key와 Value를 가진 데이터를 추가한다. 이미 있는 Key를 추가하는 입력은 주어지지 않는다.
• 2 Key Value: 주어진 Key로 검색한 데이터의 Value를 주어진 Value로 바꾼다. 조건을 만족하는 유일한 Key가 없으면 이 명령을 무시한다.
• 3 Key: 주어진 Key로 검색한 데이터를 출력한다.

검색은 이렇게 한다. 저장된 Key 가운데 입력한 Key와의 차이가 $K$ 이하인 것만 후보로 두고, 그중 차이가 가장 작은 Key를 고른다. 차이가 가장 작은 후보가 둘이면 검색 결과는 유일하지 않다.

3 명령마다 한 줄에 결과를 출력한다.

검색 결과가 유일하면 그 데이터의 Value를 출력한다. 차이가 $K$ 이하인 Key가 하나도 없으면 -1을 출력한다. 차이가 가장 작은 Key가 둘이면 ?를 출력한다.