다리와 터널

지금은 따뜻하게 느껴질지 몰라도 몇 달 뒤면 캠퍼스는 눈으로 뒤덮인다. 다행히 캠퍼스의 많은 건물이 다리와 터널로 이어져 있어서 밖으로 나갈 일이 그리 많지 않다. 건물들의 연결망은 헷갈리기 쉬워서 한 건물에서 다른 건물로 가는 가장 좋은 길을 알기 어렵다. 컴퓨터 프로그램이 있으면 도움이 될 것이다.

입력의 첫 줄에는 세 정수 $n$, $m$, $p$ ($0 < n \le 4000$, $0 < m \le 40000$, $0 < p \le 30$)가 주어진다. 각각 캠퍼스의 건물 수, 건물들을 잇는 (실내 또는 실외) 경로의 수, 그리고 당신이 하려는 이동의 수이다. 건물은 $0$번부터 $n-1$번까지 차례로 번호가 매겨져 있다.

이어지는 $m$개의 줄은 각각 세 정수와 한 글자로 두 건물 사이의 경로를 설명한다. 처음 두 정수는 그 경로가 잇는 두 건물을 나타내며, 경로는 양방향으로 이용할 수 있다. 세 번째 정수는 한 건물에서 다른 건물로 그 경로를 지나는 데 걸리는 시간(초)으로, $0$ 이상 백만 이하이다. 마지막 글자는 경로가 실내이면 I, 실외이면 O이다.

그다음 $p$개의 줄은 각각 두 정수, 즉 두 건물의 번호로 한 건물에서 다른 건물로의 이동을 설명한다.

각 이동에 대해, 지정된 두 건물 사이의 최적 경로를 찾는다. 최적 경로는 밖에서 보내는 시간을 최소화한다. 밖에서 보내는 시간이 같은 경로들 중에서는, 전체 소요 시간을 최소화하는 것이 최적 경로이다.

각 이동에 대해, 밖에서 보낸 시간과 최적 경로의 전체 소요 시간, 두 정수를 한 줄에 출력한다. 만약 두 건물을 잇는 경로가 없다면, 대신 IMPOSSIBLE이라는 단어가 있는 줄을 출력한다.