Giáng sinh đã đến gần, Nghĩa bắt đầu sửa soạn trang trí cho cây thông Noel của mình.

Những năm trước, Nghĩa thường dùng ~k~ chiếc đèn LED để chiếu sáng cho cây thông; tuy vậy, để ăn mừng chức vô địch ICPC Cần Thơ mới đây của đội EggCentroy (chú thích: không phải đội của Nghĩa), Nghĩa quyết định năm nay sẽ thay ~k~ đèn LED bằng ~n~ quả trứng phát sáng. Những quả trứng này phát sáng một cách tự nhiên, không cần sử dụng năng lượng điện, tuyệt đối thân thiện với môi trường. Nghĩa treo ~n~ quả trứng này thành một hàng ngang. Không may thay, sau khi trang trí xong, Nghĩa mới phát hiện ra rằng trong quá trình vận chuyển, một số quả trứng đã bị úng nước và không thể phát sáng được. Vì cấu trúc cây thông Noel của Nghĩa vô cùng phức tạp nên cậu không thể tháo những quả trứng bị hỏng ra được. Tuy nhiên, bằng trí tuệ đỉnh cao của người từng 2 lần đạt giải Nhất kì thi Xếp trứng giỏi Quốc gia, Nghĩa đã tìm thấy ~m~ cặp vị trí ~(a_1, b_1), (a_2, b_2), \dots, (a_m, b_m)~ mà cậu có thể đổi chỗ quả trứng ở vị trí thứ ~a_i~ với quả trứng ở vị trí thứ thứ ~b_i~ ~(1 \leq i \leq m)~. Lưu ý rằng Nghĩa có thể đổi chỗ những cặp trứng này một số lần tùy ý. Ngoài ra, Nghĩa có thể đặt một vài trong số ~k~ chiếc đèn LED của mình vào những quả trứng bị hỏng để thắp sáng chúng.

Tất nhiên, chừng đó có thể là không đủ để thắp sáng tất cả các quả trứng, do đó Nghĩa muốn sửa lại dãy trứng của mình sao cho có một đoạn liên tiếp các quả trứng phát sáng dài nhất có thể. Nói cách khác, Nghĩa muốn chọn đoạn ~[l..r]~ dài nhất sao cho tồn tại một cách đổi chỗ và thắp sáng để tất cả các quả trứng từ ~l~ đến ~r~ đều phát sáng. Nghĩa đã nghĩ ra thuật toán để tính đáp án, nhưng vì Kiên và Thế đang đi du lịch Bangladesh nên không ai chịu code hộ Nghĩa cả, các bạn hãy giúp Nghĩa nhé!

Input

Dòng đầu tiên gồm ba số nguyên ~n~, ~m~, ~k~ (~1 \leq n \leq 5 \times 10^5~, ~0 \leq m \leq 5 \times 10^5~, ~0 \leq k \leq n~), lần lượt là số quả trứng, số cặp vị trí có thể đổi chỗ cho nhau, và số đèn LED Nghĩa có.

Dòng thứ hai gồm một xâu kí tự ~s~ độ dài ~n~ chỉ gồm các chữ số 0 và 1, ~s_i = 0~ thể hiện quả trứng ở vị trí thứ ~i~ bị hỏng, ~s_i = 1~ thể hiện quả trứng ở vị trí thứ ~i~ đang phát sáng.

Dòng thứ ~i~ trong ~m~ dòng tiếp theo gồm hai số nguyên ~a_i~, ~b_i~ (~1 \leq a_i, b_i \leq n~, ~a_i \neq b_i~), thể hiện rằng quả trứng ở vị trí thứ ~a_i~ có thể đổi chỗ với quả trứng ở vị trí thứ ~b_i~.

Output

Nếu không tồn tại đoạn ~[l..r]~ nào thỏa mãn đề bài, in ra ~-1~.

Ngược lại, in ra trên một dòng hai số nguyên dương ~l~, ~r~, thể hiện đoạn dài nhất thỏa mãn đề bài. Nếu có nhiều đoạn dài nhất, in ra đoạn có ~l~ nhỏ nhất.

Giới hạn

• ~10\%~ số điểm có ~m = 0~, ~k = 0~.
• ~15\%~ số điểm tiếp theo có ~m = 0~.
• ~15\%~ số điểm tiếp theo có ~n \leq 500~.
• ~20\%~ số điểm tiếp theo có đáp án thỏa mãn ~l = 1~.
• ~40\%~ số điểm còn lại không có ràng buộc gì thêm.

Sample Input 1

5 3 1
00101
1 2
2 3
3 5

Sample Output 1

1 3

Sample Input 2

5 0 3
11010

Sample Output 2

1 5

Note

Ở ví dụ thứ nhất, Nghĩa có thể thực hiện lần lượt các thao tác sau:

• Đổi chỗ quả trứng thứ ~2~ và quả trứng thứ ~3~, dãy trạng thái sau khi đổi chỗ là ~s = 01001~.
• Đổi chỗ quả trứng thứ ~1~ và quả trứng thứ ~2~, ~s = 10001~.
• Đổi chỗ quả trứng thứ ~3~ và quả trứng thứ ~5~, ~s = 10100~.
• Thắp sáng quả trứng thứ ~2~, ~s = 11100~.

Lưu ý rằng, Nghĩa cũng có thể chọn đoạn ~[2..4]~ và đoạn ~[3..5]~ để thắp sáng, nhưng đoạn có độ dài ~3~ với ~l~ nhỏ nhất là đoạn ~[1..3]~.

Ở ví dụ thứ hai, Nghĩa có thể dùng ~2~ chiếc đèn LED để thắp sáng ~2~ quả trứng bị hỏng. Lưu ý rằng Nghĩa không nhất thiết phải sử dụng tất cả các đèn LED.