Bối cảnh
Tại vương miện số học LQDOJ, Prototype đang canh giữ một dãy gồm \(n\) viên ngọc ma thuật. Mỗi viên ngọc có một mức năng lượng là \(a_i\). Tuy nhiên, phù thủy uou đã thực hiện một lời nguyền cổ xưa lên dãy ngọc này. Lời nguyền mang tên "Sự suy tàn của Phi". Mỗi khi uou vung trượng, năng lượng của các viên ngọc trong một phạm vi nhất định sẽ bị hấp thụ và biến đổi theo quy tắc của hàm Phi Euler. Năng lượng sẽ giảm dần cho đến khi chạm mức tối thiểu là 1 — lúc đó viên ngọc sẽ trở thành một viên đá bình thường và không thể bị hút thêm năng lượng được nữa.
Nhiệm vụ của bạn
Bạn vào vai một nhà tiên tri. Prototype liên tục hỏi bạn về tổng năng lượng còn lại của một đoạn ngọc để chuẩn bị cho cuộc phản công. Bạn phải phản hồi thật nhanh trước khi uou hoàn tất lời nguyền.

Input

• Dòng 1: \(n\) và \(q\) (\(n, q \le 2 \cdot 10^5\)).
• Dòng 2: \(n\) số nguyên \(a_1, a_2, \dots, a_n\) (\(a_i \le 10^6\)) — năng lượng ban đầu của \(n\) viên ngọc.
• \(q\) dòng tiếp theo là các truy vấn:
  • \(1 \ l \ r\) : uou tung lời nguyền, tất cả viên ngọc từ vị trí \(l\) đến \(r\) bị biến đổi: \(a_i = \phi(a_i)\).
  • \(2 \ l \ r\) : Prototype hỏi tổng năng lượng từ vị trí \(l\) đến \(r\).

Output

• Với mỗi câu hỏi của Protoype, in ra một số nguyên duy nhất là tổng năng lượng.

Example

4 3
10 10 10 10
2 1 4
1 2 3
2 1 4

40
28

Scoring

• Subtask 1 (\(30\%\) điểm): \(n, q ≤ 1000, a ≤ 10^3\).
• Subtask 2 (\(20\%\) điểm): \(n, q ≤ 2 ⋅ 10^5, a ≤ 2\).
• Subtask 3 (\(50\%\) điểm): \(n, q ≤ 2 ⋅ 10^5, a ≤ 10^6\).