Alice có \(n\) mảnh đất được đánh số từ \(1\) tới \(n\), mảnh đất thứ \(i\) có giá trị \(a_i\).

Alice chuẩn bị cho \(q\) cuộc đàm phán độc lập với nhau. Trong mỗi cuộc đàm phán, mỗi mảnh đất được gán một hệ số, ban đầu tất cả hệ số đều bằng \(0\). Cuộc đàm phán gồm \(t\) lợi ích; mỗi lợi ích cho bởi hai số nguyên \(x\) và \(y\), có nghĩa là: mọi vị trí \(j\) mà \(j\) chia hết cho \(x\) sẽ được cộng thêm \(y\) vào hệ số của nó.

Sau khi áp dụng hết \(t\) lợi ích, Alice được sắp xếp lại \(n\) giá trị \(a_1, a_2, \dots, a_n\) lên \(n\) vị trí một cách tùy ý (mỗi giá trị dùng đúng một lần). Giá trị của cuộc đàm phán là tổng của hệ số nhân với giá trị đặt tại vị trí đó, lấy trên tất cả các vị trí.

Với mỗi cuộc đàm phán, hãy tìm giá trị lớn nhất mà Alice có thể đạt được. Các hệ số được đặt lại về \(0\) ở đầu mỗi cuộc đàm phán.

Input

• Dòng đầu chứa hai số nguyên \(N\) và \(Q\).
• Dòng thứ hai chứa \(n\) số nguyên \(a_1, a_2, \dots, a_N\).
• Tiếp theo là \(Q\) khối truy vấn mô tả các cuộc đàm phán. Mỗi khối truy vấn gồm:
  • Dòng đầu tiên của khối truy vấn là hai số nguyên dương \(K\).
  • \(K\) dòng tiếp theo của khối truy vấn là hai số nguyên dương \(x,y\)

Output

• In ra \(Q\) dòng, dòng thứ \(i\) là giá trị lớn nhất của cuộc đàm phán thứ \(i\).

Constraints

• \(1 \le n \le 10^5\)
• \(1 \le q \le 10^4\)
• \(1 \le a_i \le 10^9\)
• \(1 \le t \le 10\)
• \(1 \le x \le 100, 1 \le y \le 100\)

Example

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

64
118

1 2
42
2
2 100
3 100
1
1 7

0
294

Scoring

• Subtask \(1\) \((25\%\) số điểm\()\): \(Q=1,K=1\)
• Subtask \(2\) \((25\%\) số điểm\()\): \(Q=1,K=2\)
• Subtask \(3\) \((25\%\) số điểm\()\): \(K=3\)
• Subtask \(4\) \((25\%\) số điểm\()\): Không có ràng buộc gì thêm.