Vào ngày Halloween năm 2021, Pusheen - một chú mèo thích đồ ngọt, rất muốn nhận được kẹo từ những người bạn của mình. Vì vậy DangHung845 đã thiết kế một trò chơi như sau để Pusheen có thể nhận được kẹo từ bạn ấy:

• DangHung845 cung cấp cho Pusheen một dãy ~N~ chiếc kẹo được dán nhãn bằng những con số nguyên dương ~A_1, A_2, ..., A_N~.
• Sau đó, DangHung845 đưa ra ~Q~ thử thách, mỗi thử thách có dạng như sau:
  • DangHung845 đưa một giỏ kẹo cho Pusheen, giỏ kẹo này có chỉ số đặc biệt là ~X~, chỉ số này có ý nghĩa rằng chiếc giỏ này sẽ chỉ chứa được những chiếc kẹo được dán nhãn ~Y~ sao cho ~gcd(X, Y) > 1~.
  • Tiếp theo, bạn ấy đặt vách ngăn tại hai vị trí ~L~ và ~R~. Sau đó, DangHung845 chọn tất cả các viên kẹo mà giỏ kẹo chứa được nằm giữa hai vách ngăn này (tức những viên kẹo chỉ số ~i~ sao cho ~L \le i \le R~ và ~gcd(X, A_i) > 1~), và bỏ chúng vào giỏ.
  • Cuối cùng, Pusheen phải trả lời hai câu hỏi sau: "Giá trị lớn nhất của nhãn trong các viên kẹo được bỏ vào giỏ là bao nhiêu? và "Có bao nhiêu viên kẹo trong giỏ có nhãn là giá trị lớn nhất đó?".

Vì tính tham đồ ngọt của mình, Pusheen không thể từ chối thử thách này, tuy nhiên Pusheen phải trả lời đúng ~Q~ thử thách mới có cơ hội được nhận kẹo từ DangHung845. Các bạn hãy giúp Pusheen thực hiện điều này nhé!

Dữ liệu vào

• Dòng đầu tiên: chứa hai số nguyên dương ~N, Q~ ~(1 ≤ N, Q ≤ 10^5)~, lần lượt là số viên kẹo được bày ra và số thử thách Pusheen phải trả lời.
• Dòng thứ hai: chứa ~N~ số biểu diễn dãy các viên kẹo ~A_1, A_2, ..., A_N~ ~(1 ≤ A_i ≤ 10^5)~.
• ~Q~ dòng tiếp theo: mỗi dòng chứa ~3~ số nguyên ~X, L, R~ ~(1 ≤ X ≤ 10^5, 1 ≤ L ≤ R ≤ N)~, lần lượt là chỉ số đặc biệt của giỏ kẹo và vị trí hai vách ngăn trong thử thách tương ứng. Nếu không có viên kẹo nào bỏ được vào giỏ thì in ra -1 -1.

Dữ liệu ra

• Gồm ~Q~ dòng: mỗi dòng là câu trả lời của thử thách tương ứng.

Giới hạn

• Subtask ~1~: có ~20\%~ số điểm có ~N, Q \le 4000~.
• Subtask ~2~: có ~30\%~ số điểm khác có ~A_i~ và ~X~ là các số nguyên dương chẵn.
• Subtask ~3~: ~50\%~ số điểm còn lại không có ràng buộc gì thêm.

Sample Input

5 4
9 9 15 15 25
24 2 3
17 2 3
20 1 2
6 1 2

Sample Output

15 1
-1 -1
-1 -1
9 2

Giải thích

Trong thử thách đầu tiên, các viên kẹo được bỏ vào giỏ có nhãn là ~\{A_2, A_3\} = \{9, 15\}~. Trong đó, nhãn lớn nhất là ~15~ và có ~1~ viên kẹo được dán nhãn này.