시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
5 초 128 MB 97 25 18 26.471%

문제

상근이는 "얼음을 꿈꾸다" 여행사의 사장이다. 이 여행사는 남극 근처의 섬 N개를 구매해 당일치기 여행을 제공하고 있다. 관광객들에게 가장 인기 있는 동물은 황제 펭귄으로 섬에서 쉽게 찾을 수 있다.

여행사는 점점 인기를 얻게 되었고, 이제 보트를 이용하는 것이 효율적이지 않은 상황까지 이르렀다. 상근이는 섬 사이에 다리를 건설해 관광객을 버스로 이동시키려고 한다. 상근이는 컴퓨터 프로그램을 이용해서 다리를 건설하는 과정을 관리하려고 한다.

섬은 1번부터 N번까지 번호가 매겨져 있다. 가장 처음에는 아무 다리도 없으며, 각 섬에 펭귄이 몇 마리 살고있는지는 모두 알고있다. 펭귄의 수는 변할 수 있다. 하지만, 항상 0보다 크거나 같고, 1000보다 작거나 같다.

상근이의 프로그램은 다음과 같은 세 가지 명령을 수행할 수 있어야 한다.

  • "bridge A B" - 섬 A와 B사이에 다리를 건설하는 명령이다. (A와 B는 다르다) 이전까지 지어진 다리를 이용해서 이동할 수 없는 경우에만 다리를 지어야 한다. 다리를 지어야 하면 "yes", 지을 필요가 없이 이미 이동할 수 있으면 "no"를 출력한다.
  • "penguins A X" - 섬 A에 살고있는 펭귄의 수를 다시 세보니 X마리가 되었다는 명령이다. 아무것도 출력할 필요가 없다.
  • "excursion A B" - 관광객들이 섬 A에서 시작해 B에서 끝나는 여행 경로를 이용하는 명령이다. A에서 B로 갈 수 있는 경우에는 이동하는 섬에 있는 모든 펭귄의 수를 구해 출력한다. (A와 B 포함) 이동할 수 없는 경우에는 "impossible"를 출력한다.

상근이의 프로그램을 작성하시오.

입력

첫째 줄에 섬의 수 N (1 ≤ N ≤ 30,000)이 주어진다.

둘째 줄에는 각 섬에 있는 펭귄의 수가 주어진다.

셋째 줄에는 명령의 개수 Q (1 ≤ Q ≤ 300,000)가 주어진다.

다음 Q개 줄에는 문제에서 주어진 명령 중 하나가 주어진다.

출력

"bridge"나 "excursion" 명령이 주어질 때 마다 출력한다.

예제 입력

5
4 2 4 5 6
10
excursion 1 1
excursion 1 2
bridge 1 2
excursion 1 2
bridge 3 4
bridge 3 5
excursion 4 5
bridge 1 3
excursion 2 4
excursion 2 5

예제 출력

4
impossible
yes
6
yes
yes
15
yes
15
16

힌트