Có hai mạng truyền tin ~A~ và ~B~ cùng sử dụng ~n~ trạm. Mỗi kênh nối hai trạm, thuộc đúng một trong hai mạng và có một băng thông dương. Các kênh là hai chiều.

Băng thông của một đường truyền bằng băng thông nhỏ nhất trên các kênh của đường truyền đó. Một đường truyền từ ~x~ đến ~y~ hợp lệ nếu nó có một trong ba dạng sau:

• chỉ sử dụng các kênh của mạng ~A~;

• chỉ sử dụng các kênh của mạng ~B~;

• ban đầu sử dụng các kênh của mạng ~A~, sau đó chuyển sang mạng ~B~ đúng một lần và không quay lại mạng ~A~.

Với mỗi truy vấn, hãy tìm băng thông lớn nhất của một đường truyền hợp lệ. Nếu không tồn tại đường truyền như vậy, in ra ~0~.

Input

• Dòng đầu chứa ba số nguyên ~n~, ~m~ và ~q~ (~2 \le n \le 10^5~, ~1 \le m \le 2 \cdot 10^5~, ~1 \le q \le 10^5~).

• Mỗi dòng trong ~m~ dòng tiếp theo chứa hai số nguyên ~u,v~, một số nguyên ~w~ và một ký tự A hoặc B. Dòng này mô tả một kênh thuộc mạng tương ứng nối ~u~ với ~v~, có băng thông ~w~ (~1 \le u,v \le n~, ~u \ne v~, ~1 \le w \le 10^9~).

• Mỗi dòng trong ~q~ dòng cuối chứa hai đỉnh phân biệt ~x,y~ (~1 \le x,y \le n~).

Giữa hai trạm có thể có nhiều kênh.

Output

Với mỗi truy vấn, in ra trên một dòng băng thông lớn nhất của một đường truyền hợp lệ, hoặc ~0~ nếu không tồn tại đường truyền.

Scoring

Sample Input 1

5 5 4
1 2 8 A
2 3 5 A
3 4 7 B
4 5 6 B
2 5 3 B
1 5
1 4
2 5
5 1

Sample Output 1

5
5
5
0

Notes

Với ba truy vấn đầu, có thể truyền qua trạm ~3~: đi trong mạng ~A~ đến trạm ~3~, rồi chuyển sang mạng ~B~. Băng thông nhỏ nhất trên đường đi tốt nhất là ~5~.

Từ trạm ~5~ không thể đến trạm ~1~ theo thứ tự mạng được phép, nên truy vấn cuối có đáp án ~0~.