Cho một đồ thị liên thông có số cạnh nhỏ hơn số đỉnh, đỉnh thứ ~x~ có độ tuyệt vời là một số nguyên không âm ~A_x~.

Định nghĩa độ tuyệt vời của một đường đi là tổng xor (Định nghĩa của XOR) của độ tuyệt vời của tất cả các đỉnh trên đường đi đó. Độ tuyệt vời của cặp đỉnh ~(u, v)~ là tích của độ tuyệt vời của tất cả các đường đi đơn từ ~u~ đến ~v~. Vì đồ thị là liên thông, nên luôn tồn tại ít nhất một con đường giữa cặp đỉnh ~(u, v)~. Ta cũng có thể dễ dàng chứng minh được rằng có hữu hạn đường đi đơn giữa một cặp đỉnh bất kì, nên độ tuyệt vời của một cặp đỉnh ~(u, v)~ luôn tính được.

Độ tuyệt vời của một đồ thị chính là độ tuyệt vời lớn nhất của một cặp đỉnh bất kì.

Tính độ tuyệt vời của đồ thị nêu trên, cũng như số lượng cặp ~(u, v)~ (~u \leq v~) có độ tuyệt vời đúng bằng độ tuyệt vời của đồ thị.

Ví dụ

Cho đồ thị có ~N = 3~, ~M = 3~, ~A = [1, 2, 4]~ và các cạnh nối như hình minh họa trên.

• Cặp ~(1, 1)~: Có một đường đi đơn từ ~1~ tới ~1~ là chính đỉnh ~1~. Vậy độ tuyệt vời của cặp ~(1, 1)~ là: ~1~.

• Cặp ~(2, 2)~: Có một đường đi đơn từ ~2~ tới ~2~ là chính đỉnh ~2~. Vậy độ tuyệt vời của cặp ~(2, 2)~ là: ~2~.

• Cặp ~(3, 3)~: Có một đường đi đơn từ ~3~ tới ~3~ là chính đỉnh ~3~. Vậy độ tuyệt vời của cặp ~(3, 3)~ là: ~4~.

• Cặp ~(1, 2)~: Có hai đường đi đơn từ ~1~ tới ~2~ là ~1~ → ~2~ và ~1~ → ~3~ → ~2~. Vậy độ tuyệt vời của cặp ~(1, 2)~ là: ~(A_1 \oplus A_2) \times (A_1 \oplus A_3 \oplus A_2) = 21~.

• Cặp ~(1, 3)~: Có hai đường đi đơn từ ~1~ tới ~3~ là ~1~ → ~3~ và ~1~ → ~2~ → ~3~. Vậy độ tuyệt vời của cặp ~(1, 3)~ là: ~(A_1 \oplus A_3) \times (A_1 \oplus A_2 \oplus A_3) = 35~.

• Cặp ~(2, 3)~: Có hai đường đi đơn từ ~2~ tới ~3~ là ~2~ → ~3~ và ~2~ → ~1~ → ~3~. Vậy độ tuyệt vời của cặp ~(2, 3)~ là: ~(A_2 \oplus A_3) \times (A_2 \oplus A_1 \oplus A_3) = 42~.

Như vậy, độ tuyệt vời của đồ thị là ~42~, và có một cặp có có độ tuyệt vời bằng ~42~ là ~(2, 3)~.

Input

• Dòng đầu tiên nhập vào hai số nguyên không âm ~N, M~ ~(M, N \leq 10^5)~, là số đỉnh và số cạnh của đồ thị.
• Dòng thứ hai gồm ~N~ số nguyên không âm ~A_1, A_2, ..., A_N~ ~(0 \leq A_i \leq 2^{30})~.
• ~M~ dòng tiếp theo, dòng thứ ~i~ nhập vào hai số nguyên dương ~u_i~, ~v_i~, cho biết có một cạnh nối giữa hai đỉnh ~u_i~, ~v_i~ ~(1 \leq u_i, v_i \leq N)~.
• Dữ liệu đầu vào đảm bảo các cạnh nhập vào sẽ tạo thành một đồ thị liên thông.

Output

• In ra kết quả của bài toán trên

Sample Input

5 4
10 0 15 2 6
1 2
2 3
2 4
3 5

Sample Output

15 2

Giải thích test mẫu:

Hình minh họa cho test ví dụ ở phần Sample Input.

Hai cặp ~(2, 3)~ và ~(3, 3)~ có độ tuyệt vời là ~15~. Đây cũng chính là độ tuyệt vời của đồ thị.

Scoring