Cho dãy ~a~ gồm ~n~ số nguyên dương phân biệt.

Một dãy số nguyên dương ~p_1, p_2, ..., p_k~ được định nghĩa là đẹp nếu nó thỏa mãn tính chất sau:

• ~k \ge 1~
• ~1 \le p_1 < p_2 < ... < p_k \le n~
• Tồn tại một số nguyên dương ~m \ge 2~ thỏa mãn ~a_{p_1} \equiv a_{p_2} \equiv ... \equiv a_{p_k}~ ~(mod~ ~m)~.

Hãy tìm dãy đẹp dài nhất có thể.

Input

• Dòng đầu gồm số nguyên dương ~n~. ~(n \le 10^5)~
• Dòng thứ hai gồm ~n~ số nguyên dương miêu tả dãy ~a~. ~(a_i \le 10^{12})~
• Dữ liệu đảm bảo rằng dãy ~a~ gồm các số phân biệt.

Output

• Dòng đầu tiên in ra hai số ~k~ và ~m~ lần lượt là độ dài của dãy lớn nhất tìm được và số ~m~ thỏa mãn.
• Dòng thứ hai in ra dãy ~p_1, p_2, ..., p_k~ miêu tả dãy đẹp tìm được.
• Nếu có nhiều dãy đẹp dài nhất thỏa mãn, in ra một dãy bất kì.

Subtask

• ~10\%~ số test có ~n \le 20~
• ~20\%~ số test có ~a_i \le 100~.
• ~30\%~ số test có ~n \le 50~.
• ~40\%~ số test còn lại không ràng buộc gì thêm.

Sample Input 1

5
1 5 2 4 6

Sample Output 1

3 2
3 4 5 

Sample Input 2

7
2 5 3 8 6 11 14 

Sample Output 2

5 3
1 2 3 6 7

Đại dịch Chow đã quay trở lại HNAMS.

Lần này, nó mang tới một biến thể virus mới với chu kì bệnh trong ~k~ ngày, sau khoảng thời gian đó, bệnh nhân được coi là đã không còn nhiễm dịch nữa. Do đây là một đại dịch nguy hiểm, chính phủ sẽ bảo đam an toàn bằng cách đánh dấu những người có thể nhiễm bệnh, đó là những người có liên hệ trực tiếp hoặc gián tiếp đối với người bệnh trong ~k~ ngày gần nhất (không phụ thuộc vào thứ tự liên hệ).

Chow là một căn bệnh rất lạ, bởi không ai có cơ chế miễn dịch với nó cả.

Bạn cần viết ra một chương trình để tính toán số người có khả năng nhiễm bệnh của một người được cho (nói cách khác là tính số người đã liên hệ với người được cho trong ~k~ ngày gần nhất).

Được biết, đất nước HNAMS có ~n~ người, và có ~q~ sự kiện như sau:

• ~1~ ~(x,y):~ người ~x~ và người ~y~ gặp nhau ~(x \neq y)~.
• ~2~ ~z:~ Hãy trả về số người có thể bị lây bệnh bởi ~z~ (tính cả ~z~).
• ~3~ ~:~ ngày hiện tại kết thúc, chuyển sang ngày mới.

Input

• Dòng đầu tiên chứa ba số nguyên dương ~n,q,k~, lần lượt là số người, số sự kiện và số ngày trong chu kì bệnh ~(1 \le n \le 10^5; 1 \le q \le 5 \times 10^5; 1 \le k \le 10^5)~
• ~q~ dòng sau, mỗi dòng chứa một sự kiện ở một trong ~3~ dạng:
  • ~1~ ~(x,y):~ người ~x~ và người ~y~ gặp nhau ~(x \neq y)~.
  • ~2~ ~z:~ Hãy trả về số người có thể bị lây bệnh bởi ~z~ (tính cả ~z~).
  • ~3~ ~:~ ngày hiện tại kết thúc, chuyển sang ngày mới.

Output

• Với mỗi truy vấn dạng ~2~, in ra kết quả.

Subtask

• Sub ~1~ ~(50\%)~: ~1 \le n,q \le 1000~
• Sub ~2~ ~(50\%)~: Không có ràng buộc gì thêm.

Sample Input 1

10 27 2
1 3 9
2 9
1 1 3
1 3 1
2 4
1 3 8
1 6 5
3
1 9 2
1 8 3
2 9
1 3 1
2 5
1 4 6
3
3
2 4
3
1 9 10
1 7 1
3
2 2
3
1 5 6
1 1 4
3
2 6

Sample Output 1

2
1
5
2
1
1
2

Cho dãy số nguyên dương ~a_1,a_2,...,a_n~ và một số ~k~.

Một tập con ~S~ của ~\{1,2,...,n\}~ được gọi là tập ~xor~ nếu ~S~ không có quá ~k~ phần tử và với mọi ~i,j~ thuộc ~S~ ta có ~a_i + a_j = a_i \oplus a_j~, với ~\oplus~ là phép ~xor~.

Trọng số của ~S~ được hiểu là ~\sum a_i, \forall i \in S~.

Input

• Dòng đầu tiên chứa số nguyên dương ~n~.
• Dòng thứ hai chứa số nguyên dương ~k~.
• Nếu ~n \le 10^4~ thì có dòng thứ ba, ngược lại không có.

Output

• Ghi ra tổng trọng số tất cả các tập ~xor~, sau khi lấy dư cho ~10^9+7~.

Subtask

• Sub ~1~ ~(20\%)~: ~1 \le n,k,a_i \le 10^2~
• Sub ~2~ ~(20\%)~: ~1 \le n,k,a_i \le 10^3~.
• Sub ~3~ ~(20\%)~: ~1 \le n,k \le 10^4~ và ~a_i = i~.
• Sub ~4~ ~(20\%)~: ~1 \le n,k,a_i \le 10^4~.
• Sub ~5~ ~(20\%)~: ~1 \le n,k \le 10^{1000}~ và ~a_i = i~.

Sample Input 1

6 
3
1 1 2 3 4 5

Sample Output 1

66

Mùa đông đang đến (hoặc có thể sẽ đi? Ai có thể chắc chắn được những ngày này đây) và một vị vua mới trỗi dậy ở phương Bắc. Thông điệp được truyền đi nhanh chóng trong những ngày này... Đó là lý do tại sao bạn, vị vua đang nổi lên, không còn nhiều thời gian nữa. Bạn cần tập hợp các chư hầu của mình. Tuy nhiên, nảy sinh ra một vấn đề. Bạn có thể chiếm đóng một vương quốc rộng lớn đến mức nào và bạn nên cử đi bao nhiêu người? Các quân sư của bạn đã xem xét kỹ những mảnh đất tiềm năng và đã xác định có bao nhiêu chư hầu của bạn sẽ được triệu tập để bảo vệ vương quốc mới của bạn. Vì bạn là một vị vua anh minh, bạn muốn giảm thiểu tối đa số lượng quân lính phải phục vụ trong quân đội của mình và thông báo điều đó tới hội đồng quân sư.

May mắn thay, kẻ thù của bạn vẫn còn khá yếu kém. Bạn chỉ cần phải đối mặt với một đội quân chỉ biết đi ngang và đi dọc (đối phương sẽ không thể đi chéo). Vương quốc của bạn được tính là được bảo vệ nếu không có một cách nào để tiến đánh vào kinh đô, dù xuất phát từ bất kì nơi đâu ở ngoài bản đồ và không vượt qua các vùng được bảo vệ. Các ô vuông ở trên bản đồ được đánh số là ~0~ nếu đó là núi, sẽ không ai có thể vượt qua được đó nên bạn không cần cử người bảo vệ. Và, do bạn không chắc chắn về những gì ẩn nấp sau đường biên giới (hoặc trong trường hợp này là đường viền của bản đồ), bạn phải giả định điều tồi tệ nhất và lên kế hoạch để bảo vệ kinh đô của mình.

Input

• Dòng đầu tiên gồm ~2~ số nguyên dương ~n,m~ miêu tả số hàng và số cột của bản đồ.
• ~n~ dòng sau, mỗi dòng gồm ~m~ số nguyên không âm miêu tả bản đồ. Ô trên dòng thứ ~i~ và cột ~j~ có giá trị là ~a_{i,j}~, có nghĩa là số người cần thiết để bảo vệ ô ~(i,j)~. Nếu ~a_{i,j} = 0~ nghĩa là đây là núi và bạn không cần cử ai để bảo vệ nó.
• Dòng cuối cùng gồm ~2~ số nguyên ~r,c~ miêu tả vị trí kinh đô của bạn.

Output

• In ra số quân ít nhất bạn cần huy động để có thể bảo vệ kinh đô.

Constraints

• ~1 \le n,m \le 300~
• ~1 \le a_{i,j} \le 10^5~.
• ~0 \le r \le n-1, 0 \le c \le m - 1~.

Sample Input 1:

7 8
42 42  0  0  0  0  0 16
77 11 14 42 42 42 10 16
88  0 42 47 42 65  0 16
42  0 44 42 39 42  0 94
76  0 38 42 42 87  0 42
77 11 42 42 42  5  5 42
42 42 0 0 0 42 76 88
3 4

Sample Output 1:

37

Explanation 1:

Dấu ~x~ là những ô cử quân tới để bảo vệ, những ô đen là những dãy núi và kí hiệu tòa thành chính là kinh đô.

Kết quả sẽ là ~37~.