Trong một lớp học, cô giáo giao cho các học sinh của mình ~N~ bài tập về nhà. Bài tập thứ ~i~ yêu cầu bạn học sinh bỏ ra khoảng thời gian là ~A_i~ để hoàn thành. Tuy nhiên, không phải bất cứ bài tập nào các bạn học sinh cũng làm được, họ phải có năng lực ít nhất là ~B_i~ thì mới giải quyết được bài đó.

Trong lớp có ~Q~ học sinh, ta biết được năng lực của học sinh thứ ~i~ là ~X_i~ và để cho mỗi học sinh có thể dễ dàng quản lí thời gian, hãy giúp các bạn học sinh tìm xem tổng thời gian để hoàn thành tất cả các bài tập, mà học sinh đó có thể làm nhé.

Input

• Dòng đầu gồm 2 số nguyên ~N, Q~ ~(1 \le N, Q \le 10^5)~
• Dòng thứ 2 gồm ~N~ cặp số ~A_i, B_i~ ~(1 \le A_i, B_i \le 10^9)~
• ~Q~ dòng tiếp theo, mỗi dòng gồm một số nguyên dương ~X_i~ ~(1 \le X_i \le 10^9)~

Output

Gồm ~Q~ dòng, dòng thứ ~i~ chứa một số nguyên là thời gian để học sinh thứ ~i~ hoàn thành hết các bài tập có khả năng làm được.

Sample Input

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

Sample Output

3
0
21
37
19

Notes

Với trường hợp ví dụ, gồm ~7~ bài tập và ~5~ học sinh:

• Học sinh thứ nhất có năng lực là ~2~, có thể làm được duy nhất bài tập thứ hai nên tổng thời gian là ~3~.
• Học sinh thứ hai có năng lực là ~1~ nên không thể làm bất kì bài tập nào được giao.
• Học sinh thứ ba có năng lực là ~5~, có thể làm được các bài ~2, 3, 4, 5~ nên tổng thời gian là ~3 + 9 + 2 + 7 = 21~.
• Học sinh thứ tư có năng lực là ~8~, có thể làm được các bài ~1, 2, 3, 4, 5, 7~ nên tổng thời gian là ~10 + 3 + 9 + 2 + 7 + 6 = 37~.
• Học sinh thứ năm có năng lực là ~4~, có thể làm được các bài ~2, 3, 5~ nên tổng thời gian là ~3 + 9 + 7= 19~.

Một hôm bạn KaJo đi xem bói, thầy bói cho bạn một dãy các chữ cái la tinh in hoa tuần hoàn dài vô hạn được đánh số từ ~0~ như sau:

~['A', 'B', 'C', 'D', ..., 'Z', 'A', 'B', 'C', ...]~

Kèm theo đó là một số nguyên dương ~M~ là mật mã của thông điệp vũ trụ. Biết thông điệp được tạo nên từ các chữ cái ở vị trí là số nguyên tố (một số nguyên tố được định nghĩa là một số nguyên dương có đúng 2 ước số là 1 và chính nó) và là ước số của số ~M~.

Hãy giúp KaJo giải mã thông điệp vũ trụ này và in ra thông điệp có thứ tự từ điển nhỏ nhất.

Input Format

• Một dòng duy nhất là số nguyên dương ~M~ (~2 \le M \le 10^{12}~).

Output Format

• Một dòng duy nhất là thông điệp vũ trụ có thứ tự từ điển nhỏ nhất.

Sample Input 1

18

Sample Output 1

CD

Sample Input 2

1450

Sample Output 2

CDF

Note:

• Ở ví dụ 1, thông điệp vũ trụ được kết hợp bởi các kí tự được đánh số ~2~ và ~3~, vì thế thông điệp có thể là ~CD~ hoặc ~DC~, ta lấy ~CD~ vì có thứ tự từ điển nhỏ nhất.

Ban đầu bạn được cho một dãy ngoặc đúng ~S~. Gọi ~S'~ là một dãy ngoặc đúng bất kì thu được bằng cách xoay tròn ~S~ với số lần tùy ý.

Nhiệm vụ là đếm số lượng ~S'~ phân biệt.

Dãy ngoặc đúng: Một dãy ngoặc ~S~ được gọi là đúng khi thỏa một trong các điều kiện:

• ~S = ( T )~ với ~T~ là một dãy ngoặc đúng.
• ~S = S_1 + S_2~ với ~S_1~ và ~S_2~ là các dãy ngoặc đúng.

Ví dụ: ~()~, ~()(())~, ~(()())~ là các dãy ngoặc đúng. ~)~, ~(()~ không phải dãy ngoặc đúng.

Xoay tròn: Một phép xoay tròn của một xâu là mang kí tự cuối của xâu đó về vị trí đầu, ví dụ ~S_1S_2..S_{n-1}S_{n}~ sau khi xoay tròn sẽ thành ~S_{n}S_1S_2..S_{n-1}~.

Ví dụ: ~(())~ sau khi xoay tròn sẽ thành ~)(()~.

Input

Dòng đầu chứa số nguyên dương ~N~ - độ dài của dãy ngoặc đúng ~S~.

Dòng thứ hai chứa dãy ngoặc đúng ~S~ bất kì.

Output

Số lượng ~S'~ phân biệt là dãy ngoặc đúng thu được khi xoay tròn ~S~.

Scoring

• Subtask 1 (50%): ~|S| \leq 2 * 10^3~
• Subtask 2 (50%): ~|S| \leq 2 * 10^6~

Sample input 1

4
(())

Sample output 1

1

Sample input 2

6
()(())

Sample output 2

2

Notes

Ở ví dụ 1 chỉ duy nhất ~(())~ là dãy ngoặc đúng.

Ở ví dụ 2 có 2 dãy ngoặc đúng là ~()(())~ và ~(())()~.

Mô tả đề bài

~A~ và ~B~ là 2 nhân viên làm game đã xuất sắc hoàn thành nhiệm vụ được giao. Và trong năm nay, họ lên kế hoạch tạo ra 1 trò chơi mô phỏng lại trò chơi kéo búa bao tuổi thơ.
Đây là 1 tựa game online chiến thuật, 2 người chơi sẽ thi đấu với nhau bằng 1 bộ bài rất đặc biệt. Bộ bài có tổng cộng ~2*N~ lá bài, gồm 3 loại lá bài: kéo, búa và bao.
Mỗi người chơi sẽ được phát ~N~ lá, trò chơi sẽ bắt đầu theo luật sau:

• Trò chơi có ~N~ lượt, mỗi lượt cả hai sẽ đánh bất kỳ của mình xuống và so sánh với nhau theo luật búa thắng kéo, kéo thắng bao, bao thắng búa
• Sau khi so sánh, nếu hòa, cả hai sẽ không được điểm, nếu lá bài bên nào thắng thì bên đó sẽ được cộng ~1~ điểm
• Lá bài nào đã được đánh xuống sẽ không được phép dùng lại

Sau khi hoàn thành, ~A~ và ~B~ quyết định chơi thử với nhau để tìm ra các lỗi trước khi phát hành.
Khi đang test, ~A~ phát hiện ra rằng anh có thể thấy được tất cả lá bài trên tay của ~B~ cũng như là các lá mà ~B~ sẽ chọn trong mỗi lượt. Thay vì thông báo cho ~B~ biết và cùng nhau sửa lỗi, ~A~ muốn ~B~ phải khả năng trầm trồ vì sự may mắn của bản thân. Vì vậy ~A~ đã âm thầm tận dụng lỗi này để chiến thắng ~B~ một cách áp đảo.

Tìm khoảng cách điểm tối đa của ~A~ so với ~B~ khi trò chơi kết thúc.

Input format

• Dòng đầu tiên là số nguyên ~N~ ~(1 \le N \le 10^6)~
• Dòng thứ hai là ~N~ kí tự cách nhau bởi 1 khoảng trắng tương ứng ~N~ lá bài phát cho ~A~
• Dòng thứ ba là ~N~ kí tự cách nhau bởi 1 khoảng trắng tương ứng ~N~ lá bài phát cho ~B~
• Dòng thứ 2 và thứ 3 chỉ chứa các kí tự ~R, S, P~ tương ứng búa, kéo và bao

Output format

• In ra duy nhất 1 số nguyên là giá trị lớn nhất của (điểm ~A~ - điểm ~B~)

Constraints

Subtask 1 (gồm 30% số điểm): ~N \le 18~
Subtask 2 (gồm 70% số điểm): ~N \le 10^6~

Sample Input 1:

3   
R P S  
P P P

Sample Output 1:

0

Sample Input 2:

4   
P R R P  
R R S S  

Sample Output 2:

4

Giải thích ví dụ

Testcase 1
Cách chơi tối ưu của ~A~:

• Nếu ~B~ chọn lá bài ~P~ đầu tiên, ~A~ sẽ chọn lá bài ~P~ duy nhất của mình. ~A~ hòa nên được 0 điểm.
• Nếu ~B~ chọn lá bài ~P~ thứ 2, ~A~ sẽ chọn lá bài ~S~ duy nhất của mình. ~A~ thắng được 1 điểm.
• Nếu ~B~ chọn là bài ~P~ thứ 3, ~A~ sẽ chọn lá bài ~R~ duy nhất của mình. ~A~ thua nên được 0 điểm.
  Vậy khoảng cách là ~1-1 = 0~.

Testcase 2
Cách chơi tối ưu của ~A~:

• Nếu ~B~ chọn lá bài ~R~ đầu tiên, ~A~ sẽ chọn lá bài ~P~ đầu tiên của mình. ~A~ thắng được 1 điểm.
• Nếu ~B~ chọn lá bài ~S~ đầu tiên, ~A~ sẽ chọn lá bài ~R~ đầu tiên của mình. ~A~ thắng được 1 điểm.
• Nếu ~B~ chọn là bài ~R~ thứ 2, ~A~ sẽ chọn lá bài ~P~ thứ hai của mình. ~A~ thắng được 1 điểm.
• Nếu ~B~ chọn là bài ~S~ thứ 2, ~A~ sẽ chọn lá bài ~R~ thứ hai của mình. ~A~ thắng được 1 điểm.
  Vậy khoảng cách là ~4-0 = 4~.

ZaloPay là ứng dụng thanh toán di động với nhiều tính năng độc đáo. Được xây dựng chuyên biệt để thỏa mãn mọi nhu cầu thanh toán trong cuộc sống và nhu cầu kinh doanh... Ngoài việc sử dụng ứng dụng ZaloPay trên điện thoại hay sử dụng ZaloPay trực tiếp trên ứng dụng Zalo, bây giờ người dùng có thể truy cập website ZaloPay tại đây để biết thêm các thông tin cũng như sử dụng cách dịch vụ ngay trên website như thanh toán hoá đơn, nạp tiền điện thoại, mua vé xem phim, ...

ZaloPay không chỉ cung cấp các giải pháp thanh toán thông minh mà còn đặc biệt chú trọng đến vấn đề bảo mật thông tin. Một trong những phương pháp bảo mật phổ biến nhất là mã hóa dữ liệu. Mã hóa dữ liệu biến đổi thông tin thành dạng không thể đọc được nếu không có khóa giải mã, giúp bảo vệ thông tin khỏi các cuộc tấn công và truy cập trái phép.

Thông tin người dùng gửi lên được thể hiện bởi một dãy gồm ~N~ số nguyên dương ~a_1, a_2, a_3, ..., a_N~, sau đó máy chủ sẽ tiến hành mã hoá thông tin và tạo ra một số nguyên ~A~ bằng cách tính tích các số trong dãy trên. Để giải mã thông tin được mã hoá trên, bạn cần phải có khoá bí mật, được đại diện bởi một cặp số nguyên dương ~(X, P)~. Một khoá được gọi là hợp lệ nếu ~A~ chia hết cho ~X^P~.

Để có thể truy cập vào tài nguyên, người dùng cần gửi kèm khoá bí mật để máy chủ xác thực. Có ~T~ truy vấn được gửi lên máy chủ, hãy cho biết khoá gửi kèm có hợp lệ hay không?

Input

• Dòng đầu chứa số nguyên dương ~N~ ~(N \le 10^6)~
• Dòng thứ hai chứa ~N~ số nguyên biểu diễn cho dãy số ~(1 \le a_i \le 10^6)~
• Dòng thứ ba chứa số nguyên dương ~T~ - là số lượng truy vấn ~(T \le 5 \times 10^5)~
• ~T~ dòng tiếp theo, mỗi dòng chứa cặp số nguyên ~X~ ~P~ ~(1 \le X, P \le 5 \times 10^5)~

Output

Gồm ~T~ ký tự viết liên tiếp nhau, ký tự thứ ~i~ là ~1~ nếu trong truy vấn thứ ~i~, ~A~ chia hết cho ~X^P~, ngược lại là ~0~

Subtasks

• Subtask 1 (20%): ~A \le 10^9~ và ~X, P \le 10^5~
• Subtask 2 (20%): mọi truy vấn đều có ~P = 1~
• Subtask 3 (20%): ~N, A, X, P \le 10^5~
• Subtask 4 (40%): không có ràng buộc gì thêm

Sample Input

5
1 2 3 4 5
4
5 1
2 3
3 4
15 2

Sample Output

1100

Notes

Trong ví dụ trên, ~A = 1 * 2 * 3 * 4 * 5 = 120~, có tất cả ~4~ truy vấn:

• Truy vấn 1, ~X = 5, P = 1~ và ~A=120~ chia hết cho ~5^1=5~
• Truy vấn 2, ~X = 2, P = 3~ và ~A=120~ chia hết cho ~2^3=8~
• Truy vấn 3, ~X = 3, P = 4~ và ~A=120~ không chia hết cho ~3^4=81~
• Truy vấn 4, ~X = 15, P = 2~ và ~A=120~ không chia hết cho ~15^2=225~