VP là một thành phố vô cùng đặc biệt. Ngoài vẻ đẹp tự nhiên thu hút khách du lịch, hệ thống giao thông cũng vô cùng đặc biệt. Thành phố được kết nối bởi ~n~ điểm với ~m~ con đường phục vụ di chuyển đảm bảo liên thông toàn thành phố. Con đường thứ ~i~ kết nối hai chiều giữa hai điểm ~u_i~ và ~v_i~ với thời gian di chuyển là ~p_i~. Tuy nhiên, trong trường hợp xấu xảy ra tắc đường, để đi hết con đường này cần thời gian là ~q_i~.

Hà là một quản lý trong một công ty vận tải, Hà đang thiết kế lộ trình cố định cho tuyến xe phục vụ đưa đón khách du lịch bắt đầu từ ~s~, di chuyển qua một số con đường và kết thúc tại điểm ~t~. Giả thiết trong trường hợp xấu nhất, chỉ có một con đường trên tuyến đường di chuyển đó gặp sự cố tắc đường.

Yêu cầu: Cho ~k~ truy vấn, mỗi truy vấn gồm ~2~ số ~s, t~ (~1 \le s, t \le n~). Với mỗi truy vấn, hãy giúp Hà lựa chọn một lộ trình cố định sao cho trong trường hợp hợp xấu nhất, tổng thời gian di chuyển của xe là nhỏ nhất.

Input

• Dòng đầu chứa ba số nguyên ~n, m, k~.
• ~m~ dòng tiếp theo, dòng thứ ~i~ chứa ~4~ số nguyên dương ~u_i, v_i, p_i, q_i~ (~u_i, v_i \le n; p_i < q_i \le 10^5, \forall i = 1, 2, ..., m~).
• ~k~ dòng cuối cùng, dòng thứ ~j~ chứa hai số nguyên dương ~s, t~ xác định thông tin trong truy vấn thứ ~j~ (~s, t \le n, \forall j = 1, 2, ..., k~).

Output

• Ghi ra ~k~ dòng, dòng thứ ~j~ đưa ra câu trả lời cho truy vấn thứ ~j~ là tổng thời gian di chuyển theo tuyến đường Hà lựa chọn trong trường hợp xấu nhất.

Sample Input 1

4 5 3
1 2 2 3
1 3 8 10
1 4 3 4
3 4 4 6
2 3 1 12
1 3
2 4
2 3

Sample Output 1

9
6
11

Giải thích ví dụ

• Để di chuyển từ ~1~ tới ~3~ ta có ~3~ cách đi.
  • Với cách đi ~1 \to 3~ trong trường hợp xảy ra tắc thời gian di chuyển là ~10~.
  • Với cách đi ~1 \to 2 \to 3~ trong trường hợp xấu tắc ở đường ~1 \to 2~ thì thời gian là ~3 + 1 = 4~ nhưng trong trường hợp tắc ở đường ~2 \to 3~ thì thời gian là ~2 + 12 = 14~.
  • Với cách đi ~1 \to 4 \to 3~, trong trường hợp xấu xảy ra tắc ở đường ~1 \to 4~ thì thời gian là ~4 + 4 = 8~, trong trường hợp tắc ở ~4 \to 3~ thì thời gian là ~3 + 6 = 9~. Trong trường hợp xấu nhất thời gian di chuyển là ~9~.
• Vậy với truy vấn ~1 \to 3~ chọn đường Hà lựa chọn trong trường hợp xấu nhất thời gian di chuyển là ~9~.

Subtasks