만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

올드 오르헤이 (Old Orhei)

면접 대비

시간 제한3초메모리 제한2048 MB

요약
간선 번호가 담긴 배열의 구간대로 방향 그래프를 따라 이동했을 때 최종 정점을 구하고, 배열 값을 바꾸는 갱신을 처리합니다.
난이도

보통10점 중 5점

유형
세그먼트 트리, 배열
정답자
아직 제출이 없습니다

문제

Old Orhei(Orheiul Vechi)는 Răut 강의 좁은 굽이에 있는 자연 및 역사 유적지이다. 이곳에는 NN개의 고고학 유적과, 일부 유적 쌍을 잇는 MM개의 단방향 도로가 있다. 각 도로에는 입력 순서에 따라 1부터 MM까지의 고유한 번호가 붙는다.

Cucuteni-Trypillia 문명이 남긴 배열이 최근 현지 과학자들에 의해 발견되었다. 이 배열은 1부터 MM 사이의 값을 갖는 TT개의 정수로 이루어져 있다. 배열의 의미를 알아내기 위해 새로운 인턴이 다음 절차를 따른다.

처음에 인턴은 어떤 초기 유적에서 출발한다. 다른 과학자들은 배열의 연속된 부분 배열을 첫 원소부터 차례로 한 번에 하나씩 인턴에게 방송한다. 인턴은 방송된 번호마다 다음 규칙에 따라 위치를 바꾼다.

  • 현재 방송된 번호와 같은 번호의 도로를 사용할 수 있으면(즉, 인턴의 현재 위치가 그 도로의 시작점이면), 인턴은 그 도로를 지나 끝점으로 이동한다.
  • 그렇지 않으면 인턴은 아무것도 하지 않고 현재 위치에 머문다.

제8회 유럽 주니어 정보올림피아드를 맞아, 현지 과학자들은 다음 QQ개의 질의에 답해 달라고 요청했다.

  • 1 L R S: 인턴이 SS번 유적에서 출발하고, 배열의 LL번째 원소부터 RR번째 원소까지의 부분 배열만 방송될 때 인턴의 최종 위치를 구한다.
  • 2 i K: 배열의 ii번째 원소를 KK로 바꾼다. 이 변경은 영구적이어서 Ai=KA_i = K가 된다.

타입 1의 모든 질의에 정확히 답하라.

입력

첫 줄에 유적의 수 NN과 단방향 도로의 수 MM이 공백으로 구분되어 주어진다.

이어지는 MM개의 줄 중 ii번째 줄에는 ii번 도로가 XiX_i에서 출발하여 YiY_i에서 끝남을 나타내는 두 정수 XiX_i, YiY_i가 주어진다. Xi=YiX_i = Y_i인 도로도 있을 수 있고, i≠ji \ne j이면서 Xi=XjX_i = X_j, Yi=YjY_i = Y_j인 도로 쌍도 있을 수 있다.

다음 줄에는 배열의 길이 TT가 주어진다.

다음 줄에는 TT개의 정수 A1,A2,…,ATA_1, A_2, \dots, A_T가 공백으로 구분되어 주어진다.

다음 줄에는 질의의 수 QQ가 주어진다.

이어지는 QQ개의 줄에는 질의가 주어진다. 형식은 1 L R S 또는 2 i K이다.

출력

타입 1의 질의마다 답을 한 줄에 하나씩 출력한다.

제한

  • 1≤N≤501 \le N \le 50
  • 1≤M,T,Q≤1051 \le M, T, Q \le 10^5
  • 1≤Xi,Yi≤N1 \le X_i, Y_i \le N
  • 1≤Ai≤M1 \le A_i \le M
  • 1≤L≤R≤T1 \le L \le R \le T
  • 1≤S≤N1 \le S \le N
  • 1≤i≤T1 \le i \le T
  • 1≤K≤M1 \le K \le M

예제3

  1. 예제 1

    입력
    5 6
1 2
3 2
4 2
2 5
5 1
4 5
6
2 1 4 2 5 3
3
1 3 5 2
1 3 5 2
1 1 2 3
    예상 출력
    1
1
2

  2. 예제 2

    입력
    3 3
1 2
2 3
3 1
4
3 1 1 2
4
1 1 2 3
2 2 2
1 1 2 3
1 1 4 2
    예상 출력
    2
1
3

  3. 예제 3

    입력
    2 3
1 1
1 2
1 2
4
1 1 2 3
3
1 1 2 1
2 1 2
1 1 2 1
    예상 출력
    1
2