Cho hai chuỗi nhị phân s và t có cùng độ dài ~n~, mỗi ký tự chỉ có thể là ~0~ hoặc ~1~, các phần tử trong hai chuỗi được đánh thứ tự từ ~1~ đến ~n~. Hai chuỗi này biểu diễn cấu hình trạng thái của hai hệ thống độc lập. Do yêu cầu đồng bộ dữ liệu, cần thực hiện các thao tác hoán đổi để đưa hai chuỗi này về trạng thái giống hệt nhau. Một thao tác được định nghĩa như sau:

• Chọn một vị trí ~i~ trong chuỗi s và một vị trí ~j~ trong chuỗi t.
• Hoán đổi giá trị ~s_i~ và ~t_j~.

Yêu cầu: Hãy xác định số thao tác ít nhất để hai chuỗi trở nên giống hệt nhau.

INPUT

• Dòng đầu chứa số nguyên dương ~n~ cho biết độ dài của hai chuỗi.
• Dòng thứ hai chứa chuỗi nhị phân s.
• Dòng thứ ba chứa chuỗi nhị phân t.

OUTPUT

• Nếu không thể hoán đổi thì ghi ra ~-1~.
• Ngược lại:
  • Dòng đầu ghi số nguyên ~k~ cho biết số thao tác ít nhất.
  • ~k~ dòng tiếp theo, mỗi dòng gồm hai số nguyên ~i~ và ~j~ cho biết hai chỉ số trong s và t được chọn ở thao tác đó. Nếu có nhiều phương án, ghi ra một phương án bất kỳ.

SAMPLE INPUT 1

4
0101
0011

SAMPLE OUTPUT 1

2
3 3
3 2

SAMPLE INPUT 2

3
000
111

SAMPLE OUTPUT 2

-1

SUBTASKS

Một công ty đang triển khai hệ thống gồm ~n~ cảm biến giám sát nhiệt độ dọc theo một con đường thẳng có độ dài ~2n~, các cảm biến được đánh thứ tự từ ~1~ đến ~n~. Cảm biến thứ ~i~ có phạm vi giám sát từ vị trí ~l_i~ đến vị trí ~r_i~ (~1 ≤ l_i < r_i ≤ 2n~), nghĩa là nó có thể đo nhiệt độ tại tất cả các điểm ~x~ sao cho ~l_i ≤ x ≤ r_i~, các mốc vị trí quản lý của tất cả các cảm biến đôi một khác nhau.

Do nhu cầu tiết kiệm năng lượng, trong mỗi ca giám sát, kỹ thuật viên chỉ bật một số cảm biến nhất định. Khi đó, vùng giám sát thực tế là hợp của tất cả các đoạn phạm vi đo của những cảm biến được bật. Các đoạn giám sát của các cảm biến được bật mà giao hoặc chạm nhau sẽ tạo thành một miền giám sát liên tục, hai đoạn cách nhau ít nhất một đơn vị sẽ được xem là hai miền liên thông riêng biệt. Số lượng các miền giám sát liên tục này phản ánh mức độ phân mảnh của vùng giám sát, và mức độ này sẽ làm tăng độ phức tạp giám sát của hệ thống. Độ phức tạp giám sát của một phương án bật cảm biến được tính bằng số miền giám sát liên tục nâng lên lũy thừa ~k~, với ~k~ là số nguyên cho trước.

Ví dụ: với hệ thống gồm ba cảm biến với phạm vi giám sát lần lượt là ~[1; 3]~, ~[2; 5]~, ~[4; 6]~ và ~k = 3~ thì:

• Với phương án bật từng cảm biến riêng thì mỗi phương án sẽ tạo được một miền giám sát liên tục nên độ phức tạp giám sát của các phương án này là ~1^3 = 1~.

• Với phương án bật cảm biến ~1~ và ~2~ hoặc bật cảm biến ~2~ và ~3~ thì sẽ tạo được một miền giám sát liên tục nên độ phức tạp giám sát của hai phương án này là ~1^3 = 1~.

• Với phương án bật cảm biến ~1~ và ~3~ thì sẽ tạo được hai miền giám sát liên tục nên độ phức tạp giám sát của phương án này là ~2^3 = 8~.

• Với phương án bật cả ba cảm biến thì sẽ tạo được một miền giám sát liên tục nên độ phức tạp của phương án này là ~1^3 = 1~.

Yêu cầu: Hãy tính tổng độ phức tạp của tất cả các phương án bật cảm biến khác rỗng.

INPUT

Dòng đầu chứa hai số nguyên dương ~n~ và ~k~.

~n~ dòng tiếp theo, dòng thứ i chứa hai số nguyên ~l_i~ và ~r_i~ (~l_i, r_i ≤ 2n~).

Ràng buộc dữ liệu vào: ~l_i ≠ l_j, r_i ≠ r_j~ (~i ≠ j; 1 ≤ i, j ≤ n~) và ~l_i ≠ r_j~ (~1 ≤ i, j ≤ n~).

OUTPUT

In ra một số là phần dư của kết quả tìm được khi chia cho ~1000000007~.

SUBTASKS

SAMPLE INPUT 1

3 3
1 3
2 5
4 6

SAMPLE OUTPUT 1

14

SAMPLE INPUT 2

4 2
5 7
2 3
1 4
6 8

SAMPLE OUTPUT 2

42

Một doanh nghiệp có ~n~ nhân viên được đánh thứ tự từ ~1~ đến ~n~, nhân viên thứ ~i~ có một chỉ số ~t_i~, cho biết thời gian ra quyết định của nhân viên là thời gian trung bình mà nhân viên thứ ~i~ này cần có để đưa ra quyết định sau khi nhận được thông tin. Chỉ số này gắn với con người, không gắn với vị trí làm việc, điều đó nghĩa là khi một nhân viên được điều chuyển sang vị trí khác, thời gian ra quyết định của nhân viên đó không thay đổi. Hiện doanh nghiệp đang có một sơ đồ quản lý và nhân viên thứ ~i~ đang ở vị trí ~i~ trong sơ đồ quản lý này. Sơ đồ quản lý này thể hiện phân cấp quản lý của các nhân viên, trong đó mỗi nhân viên có thể quản lý trực tiếp một hoặc nhiều nhân viên khác. Nếu nhân viên ở vị trí ~i~ quản lý trực tiếp nhân viên ở vị trí ~j~ và nhân viên ở vị trí ~j~ quản lý trực tiếp hoặc gián tiếp nhân viên ở vị trí ~k~, thì nhân viên ở vị trí ~i~ cũng được coi là quản lý gián tiếp nhân viên ở vị trí ~k~. Không có nhân viên nào quản lý chính bản thân mình.

Để phục vụ việc luân chuyển nhân viên ở các vị trí, quản lý doanh nghiệp cần xử lý hai loại truy vấn:

• Truy vấn loại 1: ~1~ ~u~ ~v~ – hoán đổi vị trí của nhân viên ~u~ và nhân viên ~v~.
• Truy vấn loại 2: ~2~ ~e~ – tìm thời gian ra quyết định nhỏ nhất trong số tất cả các quản lý (trực tiếp hoặc gián tiếp) của nhân viên ~e~. Nếu nhân viên ~e~ không có ai quản lý, kết quả là ~0~.

Trong quá trình luân chuyển, các quan hệ trong sơ đồ quản lý được xác định theo vị trí và hoàn toàn cố định trong suốt quá trình, chỉ có con người di chuyển giữa các vị trí.

Yêu cầu: Hãy xác định kết quả cho mỗi truy vấn loại ~2~.

INPUT

Dòng đầu chứa ba số nguyên ~n, m, q~ (~n \le 10^3~, ~m, q \le 10^5~) cho biết số nhân viên, số quan hệ quản lý trực tiếp và số truy vấn.

Dòng thứ hai chứa ~n~ số nguyên dương ~t_1, t_2, ..., t_n~, các số có giá trị không vượt quá ~10^9~ lần lượt cho biết thời gian ra quyết định của ~n~ nhân viên.

~m~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~x, y~ cho biết vị trí ~x~ quản lý trực tiếp vị trí ~y~ (~x ≠ y~, ~1 ≤ x, y ≤ n~).

~q~ dòng tiếp theo, mỗi dòng mô tả một truy vấn theo định dạng đã nêu.

OUTPUT

Gồm nhiều dòng, mỗi dòng ghi một số nguyên cho biết kết quả tìm được tương ứng với truy vấn loại ~2~ ở dữ liệu vào.

SUBTASKS

SAMPLE INPUT

7 8 10
20 33 33 19 42 22 25
1 2
1 3
2 5
3 5
3 6
4 6
4 7
6 7
2 7
1 2 4
2 7
2 5
1 1 4
2 7
1 4 7
2 2
1 3 6
2 6

SAMPLE OUTPUT

19
20
19
19
0
25