천지창조

신이 세상을 만든 첫째 날, 신은 지상을 만들고 지상에 $1$부터 $N$까지 번호가 붙은 $N$개의 성물을 서로 다른 위치에 박아 넣었다. 이로써 지상에는 각 성물을 중심으로 하는 성지가 $N$개 생겼다.

지상은 2차원 평면으로 나타낼 수 있다. $i$번 성물은 좌표 $(X_i,Y_i)$에 박혀 있다. 좌표 $(x,y)$가 $i$번 성물의 성지에 속하는 조건은 $L_i(x,y)=\sqrt{(X_i-x)^2+(Y_i-y)^2}$가 $L_1(x,y), L_2(x,y), \cdots, L_N(x,y)$ 중 최솟값이 되는 것이다. 두 성지는 같은 좌표를 공유할 수 있다. 이때 두 성지의 중심이 되는 두 성물 사이에 연결이 생긴다. 두 성지가 공유하는 점들은 선분, 반직선, 또는 직선이 된다. 신은 선분이 생기면 그 길이가 모두 $10^{-6}$ 이상이 되도록 성물을 배치했다.

각 성물에는 이름 $S_i$가 붙어 있다. $i$번 성물과 $j$번 성물이 연결되면, 두 이름이 비슷한 정도만큼 연결이 강해진다. $C(i,j)=l$은 다음을 뜻한다. $S_i$에서 길이가 $l$인 연속 부분 문자열 중 하나가 $S_j$에 연속해서 나타나고, 길이가 $l+1$인 연속 부분 문자열은 $S_j$에 하나도 나타나지 않는다. $S_i$와 $S_j$에 같은 문자가 하나도 없으면 $C(i,j)=0$이다. $i$번과 $j$번 사이에 연결이 있으면 $C(i,j)$가 연결의 세기가 된다.

신이 세상을 만든 둘째 날, 신은 천상을 만들고 천상에 $1$부터 $N$까지 번호가 붙은 $N$개의 별을 박아 넣었다. 이 별들은 지상의 성물을 본떠 만들어졌고, 성물 간 연결 중 $N-1$개를 본떠 별 사이의 연결도 만들어졌다. 하나의 성물은 하나의 별에 대응된다. $i$번 성물에 대응된 별의 번호를 $b_i$라고 한다.

신은 처음에 $1$번 성물을 본떠 $1$번 별을 만들었다. 즉 $b_1=1$이다. 그 뒤 번호 순서대로 나머지 별을 만들었다. $u(\ge 2)$번 별을 만들 때는, 이미 별을 만든 $u-1$개의 성물 중 하나와 아직 본뜨지 않은 $N-u+1$개의 성물 중 하나를 잇는 연결 가운데 다음 순서로 고른다. 먼저 연결이 가장 강한 것, 여럿이면 이미 본뜬 별의 번호가 가장 큰 것, 그것도 여럿이면 아직 본뜨지 않은 성물의 번호가 가장 작은 것이다. 이렇게 고른 연결이 본떠진 $i$번 성물과 아직 본뜨지 않은 $j$번 성물을 잇고 있다면, $j$번 성물을 본떠 $u$번 별을 만든다. 즉 $b_j=u$이다. $b_i$가 먼저 만들어진 별이므로 $b_i$를 $b_j$의 부모 별이라고 부른다.

신이 세상을 만든 셋째 날, 신은 지상에 순례자들을 만들었다.

태초가 지나고 오랜 시간이 흐른 지금, 많은 순례자가 지상을 순례하고 있다. 그중 일부는 신께 허락을 구해 천상의 길을 통해 순례하기도 한다. 어떤 순례자가 지상의 좌표 $(x_s,y_s)$에서 지상의 좌표 $(x_e,y_e)$까지 천상의 길을 통해 이동하려 한다고 하자. $(x_s,y_s)$가 $i$번 성지에 속하고 $(x_e,y_e)$가 $j$번 성지에 속하면, 순례자는 $i$번 성지에서 육체를 떠나 정신체가 되어 $b_i$번 별로 이동한다. 그다음 별 사이의 연결을 따라 $b_j$번 별로 이동하고, $j$번 성지의 좌표 $(x_e,y_e)$로 돌아와 다시 육체를 얻으면 순례를 마친다.

이렇게 순례를 마치면 육체적 피로는 없지만, 두 별 사이를 이동하는 동안 가장 멀었던 거리만큼 정신적 피로를 느낀다. 두 별 $b_i$와 $b_j$ 사이의 거리는 그 별들을 본뜬 성물의 영향을 받아 $C(i,j)\cdot[(X_i-X_j)^2+(Y_i-Y_j)^2]$이다. 순례자는 정신적 피로를 최소화하도록 순례한다.

순례자들이 천상의 길을 이용하는 동안 별들도 이동하므로 천상의 길은 계속 바뀐다. 구체적으로는 어떤 별과 부모 별 사이의 연결이 끊어지고, 새로운 부모 별과 연결이 생긴다.

태초에 천상의 길이 어떻게 구성되었는지 구하라. 또 태초 이후 천상의 길을 이용하는 순례 계획과 천상의 길의 변화가 주어질 때, 순례자들이 느끼는 정신적 피로가 얼마인지 구하라.

첫 번째 줄에 별의 개수 $N$, 순례 계획의 개수 $Q_1$, 천상의 길이 변하는 횟수 $Q_2$가 주어진다.

다음 $N$개의 줄 중 $i$번째 줄에는 $i$번 성물의 좌표를 나타내는 두 정수 $X_i$, $Y_i$($-10^6 \le X_i, Y_i \le 10^6$)와 성물의 이름 $S_i$가 주어진다. 이름은 영어 소문자로 이루어진 문자열이다. 같은 좌표에 서로 다른 두 성물이 놓이는 일은 없다.

다음 $Q_1+Q_2$개의 줄에 각각 다음 형식 중 하나로 질의가 주어진다.

1 $x_s$ $y_s$ $x_e$ $y_e$: 순례자가 지상의 좌표 $(x_s,y_s)$에서 지상의 좌표 $(x_e,y_e)$까지 천상의 길을 통해 순례를 계획한다. 이 순례를 진행할 때 느끼는 정신적 피로의 최솟값을 출력해야 한다. 입력은 $-10^6 \le x_s, y_s, x_e, y_e \le 10^6$을 만족한다. $(x_s,y_s)$와의 유클리드 거리가 $10^{-6}$ 이하인 점은 모두 하나의 성지에 속함이 보장된다. $(x_e,y_e)$도 마찬가지다.

2 $u$ $p$: $u$번 별의 부모 별이 $p$로 바뀐다. 입력은 $1 \le p < u \le N$을 만족한다.

먼저 $N-1$개의 줄에 걸쳐 태초에 천상의 길이 어떻게 구성되었는지 출력한다. $i$번째 줄에는 $i+1$번 별에 대응된 성물의 번호 $a_{i+1}$, 태초에 $i+1$번 별의 부모 별이었던 별의 번호 $p_{i+1}$, 그리고 $a_{i+1}$번 성물과 $p_{i+1}$번 별에 대응된 성물을 잇는 연결의 세기를 출력한다.

그다음 $Q_1$개의 줄에 걸쳐, 주어진 순서대로 순례 계획과 천상의 길의 변화를 처리했을 때 순례자가 느끼는 정신적 피로의 최솟값을 한 줄에 하나씩 출력한다.