Newspapers for Magicians

내 이름은 피클! 나는 최고로 전능한 지배자. 하늘처럼 강한 힘으로 명령하는 자일지니! 오너라, 오너라. 화염의 군세여. 내 부름에 응하여 그 힘을 보여라! 익스플로전!

피클은 첫 번째 평행우주의 베르제르그 왕국, 액셀 마을에 살고 있는 정말 유명한 마법사이다.

모두가 알다시피, 베르제르그 왕국은 $1$부터 $N$까지 번호가 매겨져 있는 $N$개의 마을과 서로 다른 두 마을을 연결하는 $M$개의 도로로 이루어져 있다. 연결하는 마을이 같은 서로 다른 두 도로는 존재하지 않으며, 피클은 도로 하나를 이용할 때마다 $a$원을 지불해야 한다.

또한, 이 세계는 $O$개의 평행우주와 $P$개의 웜홀로 이루어져 있다. 각 우주는 $1$부터 $O$까지 번호가 매겨져 있고, 각 평행우주에는 정확히 하나의 베르제르그 왕국이 있으며, 모든 우주의 베르제르그 왕국의 구조는 동일하다. 평행우주들은 번호순으로 인접해 있다. 구체적으로, $i$번 평행우주는 $i$가 $1$이 아닌 경우 $i-1$번 평행우주와 인접하고, $i$가 $O$가 아닌 경우 $i+1$번 평행우주와 인접하다. 웜홀들은 인접한 평행우주의 같은 번호의 마을을 연결하며, 이용하려면 $b$원을 지불해야 한다. 예를 들어, 위 그림에는 $1$번 평행우주의 $2$번 마을과 $2$번 평행우주의 $2$번 마을을 연결하는 웜홀, $2$번 평행우주의 $4$번 마을과 $3$번 평행우주의 $4$번 마을을 연결하는 웜홀 등이 있다.

어느 날, 피클은 $O$번째 평행우주의 왕도에서 마법사들의 신문을 판다는 소식을 듣고 그 신문을 사러 가기로 했다. 피클은 슈와슈와를 밀수해야 하기 때문에 신문을 사러 갈 때 돈을 최소한으로 사용해야 하지만, 물가를 잘 몰라 $a$와 $b$의 값을 정확히 알지 못했다. 그래서 피클은 당신에게 $Q$개의 가능한 $a$와 $b$ 값에 대해 필요한 비용을 알려달라고 부탁했다. 피클을 위해 최소 비용을 구해주자.

첫 번째 줄에 베르제르그 왕국의 마을의 수 $N$, 평행우주의 수 $O$, 액셀 마을의 번호 $S$, 그리고 왕도의 번호 $E$가 공백으로 구분되어 주어진다.

두 번째 줄에 도로의 수 $M$이 주어진다.

세 번째 줄부터 $M$개의 줄 중 $i$번째 줄에 도로가 잇는 두 마을의 번호 $s\_i$, $e\_i$가 공백으로 구분되어 주어진다.

그다음 줄에 웜홀의 수 $P$가 주어진다.

그다음 $P$개의 줄 중 $i$번째 줄에 웜홀의 정보 $w\_i$, $x\_i$가 공백으로 구분되어 주어지며, 이는 $w\_i$번째 우주와 $w\_i+1$번째 우주의 $x\_i$번 마을이 연결되어 있음을 의미한다. 같은 웜홀은 두 번 이상 주어지지 않는다.

그다음 줄에 쿼리의 수 $Q$가 주어진다.

그다음 $Q$개의 줄 중 $i$번째 줄에 두 정수 $a\_i, b\_i$가 공백으로 구분되어 주어진다. 이는 $i$번째 쿼리의 도로 이용 비용이 $a\_i$, 웜홀 이용 비용이 $b\_i$임을 나타낸다.

쿼리가 주어질 때마다 피클이 신문을 사러 가는 데에 드는 최소 비용을 줄 바꿈으로 구분하여 출력한다. 만약 신문을 살 수 없다면 대신 -1을 출력한다.

• $1 \le N \le 5000$
• $1 \le O \le 1000$
• $1 \le S, E \le N$
• $0 \le M \le 10^4$
• $1 \le s\_i, e\_i \le N \\, (1\le i \le M)$
• $0 \le P \le 10^4$
• $1 \le w\_i \le O-1$; $1 \le x\_i \le N \\, (1\le i \le P)$
• $1 \le Q \le 10^4$
• $0 \le a\_i, b\_i \le 100\\, (1\le i \le Q)$