천지창조

신이 세상을 만든 첫째 날에, 신은 지상을 만들고, 지상에 $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\_i(x,y)$가 $L\_1(x,y), L\_2(x,y), \cdots, L\_N(x,y)$중 최솟값이 되는 것이다. 이런 상황에서, 두 성지는 같은 좌표들을 공유할 수 있고, 이때 두 성지의 중심이 되는 두 성물 사이에는 연결이 생긴다. 두 성지가 공유하는 점들의 형태는 선분, 반직선, 혹은 직선이 되는데, 신은 선분이 생기면 길이가 모두 $10^{-6}$이상이 되도록 성물을 배치했다.

어떤 두 성물이 연결되느냐에 따라, 연결의 세기는 서로 다르다. $i$번 성물에는 $S\_i$라는 이름이 붙어 있어, $i$번 성물과 $j$번 성물이 연결되면, 두 성물의 이름이 비슷한 정도 만큼 연결이 강해진다. $S\_i$와 $S\_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$ 개의 별은 지상에 있는 $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 \leq X\_i, Y\_i \leq 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 \leq x\_s, y\_s, x\_e, y\_e \leq 10^6$를 모두 만족하는 입력이 주어지며, $(x\_s,y\_s)$와의 유클리드 거리가 $10^{-6}$ 이하인 점은 모두 하나의 성지에 속함이 보장된다. 이는 $(x\_e,y\_e)$도 마찬가지다.

2 $u$ $p$ : $u$번 별의 부모별이 $p$로 바뀐다. $1 \leq p < u \leq N$을 만족하는 입력이 주어진다.\

먼저 $N-1$ 개의 줄에 걸쳐 태초에 천상의 길이 어떻게 구성되었는지 출력한다. 이 중 $i$번째 줄에는 $i+1$번 별과 대응된 성물의 번호 $a\_{i+1}$, 태초에 $i+1$번 별의 부모 별이었던 별의 번호 $p\_{i+1}$, $a\_{i+1}$번 성물과 $p\_{i+1}$번 별에 대응 된 두 성물을 연결하는 연결의 세기를 출력해야 한다.

그리고 다음 $Q\_1$ 개의 줄에 걸쳐, 순례 계획과 천상의 길의 변화가 주어진 순서대로 순례를 진행하면 순례자가 느끼게 될 정신적 피로의 최솟값을 한 줄에 하나씩 출력한다.