Pira là một thành phố nổi tiếng với hệ thống tàu điện ngầm lâu đời và phức tạp. Thành phố có ~n~ ga tàu, được đánh số từ ~1~ đến ~n~ và ~m~ tuyến đường có số hiệu từ ~1~ đến ~m~. Tuyến đường có số hiệu ~k~ được biểu diễn bởi cặp có thứ tự gồm hai chỉ số của hai nhà ga ~(u_k, v_k)~ cho biết tuyến đường này cho phép đi từ ga ~u_k~ đến ga ~v_k~. Khi đó ta nói tuyến đường số hiệu ~k~ là đi khỏi ga ~u_k~ và đi đến ga ~v_k~. Thời gian cần thiết để mỗi chuyến tàu đi theo tuyến đường số hiệu ~k~ từ ga ~u_k~ đến ga ~v_k~ là ~t_k~ đơn vị thời gian.

Mỗi ga có các bến tàu đến tương ứng với mỗi tuyến đường đi đến nó và các bến tàu đi tương ứng với mỗi tuyến đường đi khỏi nó. Khi xây dựng hệ thống này, lãnh đạo thành phố đã nhờ các nhà khoa học tính toán và sắp xếp các vị trí đặt các bến tàu đến và các bến tàu đi trong mỗi ga sao cho hành khách dễ dàng di chuyển và tính được thời gian di chuyển theo cách lựa chọn của mình. Các nhà khoa học đã sắp xếp vị trí các bến tàu đến và đi ở mỗi ga sao cho thời gian di chuyển từ bến tàu đến của tuyến đường số hiệu ~i~ đến bến tàu đi của tuyến đường số hiệu ~j~ được tính bởi hàm ~F(i, j) = i \times \delta + j~, trong đó ~\delta~ là một thông số mà các nhà khoa học đư vào để hàm ~F(i, j)~ có thể thay đổi linh hoạt tuỳ thời điểm. Nói một cách đơn giản, nếu trên đường di chuyển hành khách theo tuyến đường ~i~ đi đến một ga nào đó và theo tuyến đường ~j~ đi khỏi ga này thì sẽ mất ~F(i, j)~ đơn vị thời gian để thực hiện việc chuyển tuyến đường. Do đó ta gọi ~F(i, j)~ là hàm chi phí thời gian chuyển tuyến để chuyển từ tuyến đường ~i~ sang tuyến đường ~j~.

Dựa vào thông tin về thời gian di chuyển trên các tuyến đường và hàm chi phí thời gian chuyển tuyến ~F(i, j)~, hành khách có thể tính được thời gian di chuyển từ một ga đến bất kỳ ga nào còn lại trong hệ thống là bằng tổng thời gian di chuyển trên các tuyến đường giữa các ga và thời gian chuyển tuyến ở mỗi ga trung gian.

Yêu cầu: Cho biết vị trí hai ga ~u~ và ~v~ trong hệ thống, hãy tính thời gian ít nhất để di chuyển từ ga ~u~ đến ga ~v~.

Input

• Dòng thứ nhất ghi các số nguyên dương ~n~, ~m~, ~u~, ~v~ và số nguyên không âm ~\delta~, trong đó ~\delta~ ~(\delta \le 100)~ là thông số xác định hàm chi phí chuyển tuyến;
• Dòng thứ ~k~ trong số ~m~ dòng tiếp theo chứa ba số nguyên dương ~u_k~, ~v_k~ và ~t_k~ mô tả thông tin về tuyến đường số hiệu ~k~ cho biết tuyến đường này cho phép di chuyển từ ga ~u_k~ đến ga ~v_k~ và ~t_k~ ~(t_k \le 10^9)~ là thời gian di chuyển qua nó, ~k = 1, 2, \ldots, m~.

Dữ liệu đảm bảo có không quá một tuyến đường đi từ ga ~p~ đến ga ~q~ với mọi ~p~ và ~q~ và không có tuyến đường nào nối một ga với chính nó. Các số trên cùng dòng được ghi cách nhau bởi dấu cách.

Output

Ghi ra một số nguyên là thời gian di chuyển tìm được. Nếu không có cách di chuyển thì ghi ra ~-1~.

Giới hạn

• Có ~40\%~ số lượng test thoả mãn điều kiện: ~n \le 10^3, m \le 10^5, \delta = 0~;
• Có thêm ~30\%~ số lượng test thoả mãn điều kiện: ~n \le 10^5, m \le 10^5, \delta = 0~;
• ~30\%~ số lượng test còn lại thoả mãn điều kiện: ~n \le 10\,000, m \le 50\,000, \delta \ge 1~.

Sample Input

5 8 1 5 1
1 2 12
1 3 13
1 4 14
4 2 14
2 3 12
2 5 12
4 5 15
3 5 16

Sample Output

31

Note

Giải thích:

• Cặp số ~a~ ~(b)~  viết bên mỗi cung trên hình vẽ minh hoạ là thời gian di chuyển và số hiệu của tuyến đường.
• Hành khách đi từ ga ~1~ đến ga ~2~ mất ~12~ đơn vị thời gian, di chuyển từ bến tàu đến của tuyến đường số hiệu ~1~ đến bến tàu đi của tuyến đường số hiệu ~6~ ở ga ~2~ mất thời gian chuyển tuyến ~(1 \times 1 + 6) = 7~ đơn vị thời gian và di chuyển từ ga ~2~ đến ga ~5~ mất ~12~ đơn vị thời gian. Tổng cộng thời gian di chuyển là: ~12 + 7 + 12 = 31~.
• Chú ý: Vẫn với ví dụ trên, nhưng thay ~\delta = 0~ thì cách đi với thời gian ít nhất từ ga ~1~ đến ga ~5~ là: ~12 + 6 + 12 = 30~.

Một xâu ký tự được gọi là xâu đối xứng nếu đọc xâu đó từ trái qua phải cũng như đọc nó từ phải qua trái ta thu được cùng một xâu. Một xâu ký tự được gọi là xâu đối xứng cấp ~0~ nếu tồn tại một cách sắp xếp lại các ký tự của nó để thu được một xâu đối xứng.

Một xâu ~s=s_1 s_2 \ldots s_n~ gồm ~n~ ký tự (ta gọi ~n~ là độ dài của xâu ~s~) được gọi là xâu đối xứng cấp ~k~ nếu nó thoả mãn các điều kiện sau:

1. ~s~ là xâu đối xứng cấp ~0~;
2. tồn tại ~k~ vị trí ~1 < i_1 < i_2 < \ldots < i_k < n~, sao cho xâu con gồm ~i_j~ ký tự đầu tiên của xâu ~s~ là xâu đối xứng cấp ~0~, ~j = 1, 2, \ldots, k~.

Dễ thấy, nếu một xâu là xâu đối xứng cấp ~k~ thì nó cũng là xâu đối xứng cấp ~m~ với ~0 \le m < k~.

Ví dụ, các xâu ada, abba là các xâu đối xứng; xâu daa là xâu đối xứng cấp 0; xâu abab là xâu đối xứng cấp ~1~ (vị trí thoả mãn định nghĩa là ~i_1 = 3~); xâu ababd là xâu đối xứng cấp ~2~ (~2~ vị trí thoả mãn định nghĩa là ~i_1 = 3~ và ~i_2 = 4~).

Ký hiệu ~S(n, k, \Omega)~ là dãy tất cả các xâu đối xứng cấp ~k~ độ dài ~n~ chỉ gồm các ký tự thuộc tập ký tự ~\Omega~ được liệt kê theo thứ tự từ điển, đánh số bắt đầu từ ~1~.

Ví dụ, với ~n = 3; \; k = 1; \;~ ~\Omega = \{\text{'v', 'n'}\}~, dãy ~S(3, 1, \{\text{'v', 'n'}\})~ gồm 4 xâu được liệt kê theo thứ tự từ điển và đánh số thứ tự bắt đầu từ ~1~ sau đây:

1. nnn
2. nnv
3. vvn
4. vvv

Yêu cầu: Cho ~n, k, \Omega~ và số nguyên ~t~, hãy đưa ra xâu thứ ~t~ trong dãy ~S(n, k, \Omega)~.

Input

• Dòng đầu chứa hai số nguyên không âm ~n, k~ ~(k \le n - 2)~;
• Dòng thứ hai chứa các ký tự của tập ~\Omega~ được ghi nhận bởi một xâu gồm không quá ~5~ chữ cái in thường lấy từ tập ~26~ chữ cái tiếng Anh từ a đến z;
• Dòng thứ ba chứa số nguyên dương ~t~ (~t~ không lớn hơn số lượng phần tử của ~S(n, k, \Omega)~).

Các số trên cùng dòng được ghi cách nhau bởi dấu cách.

Output

Ghi ra xâu thứ ~t~ của dãy ~S(n, k, \Omega)~.

Giới hạn

• Có ~20\%~ số lượng test thoả mãn điều kiện: ~2 \le n \le 10; \; \Omega = {a, b}~;
• Có ~20\%~ số lượng test khác thoả mãn điều kiện: ~2 \le n \le 10; \; k = 0~;
• Có ~20\%~ số lượng test khác thoả mãn điều kiện: ~2 \le n \le 50; \; k = 0; \; \Omega = {a, b}~;
• Có ~20\%~ số lượng test khác thoả mãn điều kiện: ~2 \le n \le 50; \; k = 0;~
• ~20\%~ số lượng test còn lại thoả mãn điều kiện: ~2 \le n \le 50~.

Sample Input

3 1
vn
2

Sample Output

nnv

Có hai hệ thống đường cao tốc được điều hành bởi hai Công ty A và B. Mỗi hệ thống đường bao gồm các nút và các đoạn đường nối các nút. Trên mặt phẳng toạ độ, các nút được biểu diễn bởi các điểm, và mỗi đoạn đường được biểu diễn bởi một đoạn thẳng nối 2 điểm tương ứng với hai nút.

Hai đoạn đường bất kỳ của hai hệ thống đường là không giao nhau ngoài ở nút đầu mút và mỗi hệ thống đường đều có tính liên thông, nghĩa là giữa hai nút bất kỳ luôn tìm được các đoạn đường liên tiếp nối chúng, và hơn nữa hai hệ thống đường là không giao nhau, tức là không tìm được nút nào thuộc cả hai hệ thống đường.

Sau một thời gian hoạt động, hai công ty A và B quyết định hợp nhất thành công ty AB nhằm nâng cao hiệu quả khai thác hệ thống đường cao tốc của họ. Vấn đề đặt ra đối với Ban Giám đốc công ty AB là hợp nhất hai hệ thống đường bằng cách xây dựng một đoạn đường thẳng nối hai nút thoả mãn các tính chất sau đây:

• Một nút thuộc hệ thống đường của Công ty A và một nút thuộc hệ thống đường của công ty B;
• Đoạn đường mới xây dựng không được có điểm chung với bất cứ đoạn đường nào của hai hệ thống đường của các công ty A và B ngoài ở hai đầu mút của đoạn đường mới này.

Yêu cầu: Giúp Ban Giám đốc công ty AB xác định đoạn đường cần xây dựng đáp ứng các yêu cầu đặt ra.

Input

• Dòng đầu tiên chứa số nguyên dương ~T~ ~(T \le 5)~ là số lượng bộ dữ liệu.

• Tiếp đến là thông tin của ~T~ bộ dữ liệu. Mỗi bộ dữ liệu bao gồm hai nhóm dòng mô tả biểu diễn trên mặt phẳng của các hệ thống đường: nhóm thứ nhất mô tả hệ thống đường của công ty A, nhóm thứ hai mô tả hệ thống đường của công ty B. Mỗi nhóm dòng có khuôn dạng như sau:

  • Dòng đầu tiên chứa hai số nguyên dương ~N~ ~(2 \le N)~ và ~M~, trong đó ~N~ là số lượng nút còn ~M~ là số lượng đoạn đường trong hệ thống. Các nút được đánh số từ ~1~ đến ~N~.
  • Dòng thứ ~i~ trnog số ~N~ dòng tiếp theo chứa hai số nguyên ~x_i~ và ~y_i~ ~(-10^6 \le x_i, y_i \le 10^6)~ là toạ độ của nút thứ ~i~, ~i = 1, 2, \ldots, N~.
  • Mỗi dòng trong số ~M~ dòng tiếp theo chứa hai số nguyên ~p~ và ~q~ ~(1 \le p, q \le N, p \ne q)~ là các chỉ số của hai nút đầu mút của một đoạn đường.

Hai số liên tiếp trên cùng dòng được ghi cách nhau bởi ít nhất một dấu cách.

Output

Ghi ra ~T~ dòng tương ứng với kết quả của ~T~ bộ dữ liệu đầu vào, mỗi dòng ghi hai số nguyên ~a~ và ~b~ cách nhau bởi một dấu cách là hai đầu mút của đoạn đường tìm được, trong đó ~a~ là chỉ số của nút thuộc hệ thống đường của công ty A và ~b~ là chỉ số của nút thuộc hệ thống đường của công ty B (nếu không tìm được đoạn đường cần xây dựng đáp ứng các yêu cầu đặt ra thì ghi ra một số ~0~; trong trường hợp bài toán có nhiều lời giải, chỉ cần đưa ra một lời giải tuỳ ý).

Giới hạn

Ký hiệu ~N_A (N_B), M_A (M_B)~ theo thứ tự là số lượng nút và số lượng đoạn đường trong hệ thống đường của công ty A (công ty B).

• Có ~40\%~ số lượng test thoả mãn điều kiện: ~2 \le N_A, M_A, N_B, M_B \le 500~;
• Có thêm ~30\%~ số lượng test thoả mãn điều kiện: ~2 \le N_A, M_A, N_B, M_B \le 5\,000~; toạ độ của các nút trong cả hai hệ thống đường có trị tuyệt đối không vượt quá ~10^4~;
• ~30\%~ số lượng test còn lại thoả mãn điều kiện: ~2 \le N_A, N_B \le 200\,000; 1 \le M_A, M_B \le 700\,000~.

Sample Input

1
5 6
0 3
1 1
6 0
5 3
9 8
1 2
1 3
4 3
3 5
1 5
2 3
4 4
6 4
4 4
4 2
2 3
1 2
4 2
2 3
3 4

Sample Output

5 2

Note