Bài tập

Cho ba xâu \(A, B, C\), thực hiện \(q\) truy vấn trên ba xâu này như sau:

• Mỗi truy vấn gồm hai số \(l, r\)
• Gọi \(x = A_{l},A_{l+1}...A_{r}\) ; \(y = B_{l}B_{l+1}...B_{r}\); \(z = C_{l}C_{l+1}...C_{r}\)
• Sắp xếp ba xâu \(x, y, z\) thành \(x′,y′,z′\)
• Gán lại các kí tự của xâu \(A\) từ \(l\) đến \(r\) thành \(x′\) , gán các kí tự của xâu \(B\) từ \(l\) đến \(r\) thành \(y′\) , gán các kí tự của xâu \(C\) từ \(l\) đến \(r\) thành \(z′\).

Hãy đưa ra ba xâu \(A, B, C\) sau khi thực hiện xong \(q\) truy vấn.

Input

Dòng đầu chứa số \(n, q\) \((1 \leq n,q \leq 10^5)\)

Ba dòng tiếp theo chứa ba xâu \(A,B,C\) có cùng độ dài chỉ chứa các kí tự thường.

\(q\) dòng tiếp theo, mỗi dòng chứa hai số \(l,r\) \((1 \leq l \leq r \leq n)\) mô tả các truy vấn.

Output

Đưa ra ba xâu trên ba dòng sau khi thực hiện xong các truy vấn.

Example

6 6
aabbcc
bcacab
cbcaba
1 1
2 2
3 3
4 4
5 5
6 6

aaaaaa
bbbbbb
cccccc

3 1
aba
aab
aac
1 3

aab
aac
aba

Scoring

\(30\%\) số điểm có \(n, q \leq 10^3\).

\(30\%\) số điểm có \(n, q \leq 10^4\).

\(40\%\) số điểm không có ràng buộc gì thêm.

Ami có một cây \(n\) đỉnh, các đỉnh được đánh số từ \(1\) đến \(n\), và ở đỉnh \(i\) chứa một số \(a_i\). Gọi \(gcd(u,v)\) là ước chung lớn nhất của tất cả các đỉnh trong đường đi từ \(u\) đến \(v\). Đường đi ở đây chỉ đi qua các đỉnh và cạnh đúng 1 lần (đường đi ngắn nhất). Gọi \(dist(u , v)\) là số đỉnh trên đường đi từ \(u\) đến \(v\). Hãy tìm 2 đỉnh \(u\) và \(v\) mà \(gcd(u,v) > 1\) và \(dist(u,v)\) đạt max.

Input

Dòng đầu tiên chứa một số nguyên dương \(n\) là số đỉnh của cây.

Dòng tiếp theo chứa \(n\) số nguyên dương \(a_i\) là số ở đỉnh \(i\).

\(N-1\) dòng tiếp theo, mỗi dòng chứa 2 số \(u\) và \(v\) là một cạnh của cây.

Output

Một dòng là đáp án.

Example

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

3

Scoring

\(2 \leq n \leq 2*10^5\).

\(1 \leq a_i \leq 2*10^5\)

Cho một dãy số \(A\) có \(N\) phần tử. Tìm số nguyên dương \(P\) nhỏ nhất thỏa mãn: \(P\) là số chính phương và \(P\) chia hết cho tất cả các phần tử của dãy số \(A\).

Yêu cầu: In ra phần dư của phép chia khi chia \(P\) cho \(10^9+7\)

Input

• Dòng đầu tiên chứa số nguyên dương \(N\) là số lượng phần tử của dãy số.

• Dòng tiếp theo chứa \(N\) số nguyên dương \(a_i\) là các phần tử của dãy số \(A\) \((1 \le i \le N)\)

Output

• Ghi ra thiết bị ra chuẩn gồm một số nguyên duy nhất là kết quả của bài toán.

Example

3
2 1 3

36

Scoring

• Subtask \(1\): Có \(30\%\) số test ứng với \(N \le 10\), \(a_i \le 10\)

• Subtask \(2\): Có \(30\%\) số test khác ứng với \(N \le 10^4\), \(a_i \le 10^5\)

• Subtask \(3\): Có \(40\%\) số test còn lại ứng với \(N \le 10^5\), \(a_i \le 10^7\)

Bạn có một số nguyên dương \(N\). Nhiệm vụ của bạn là xuất ra tất cả các số nguyên tố từ \(1\) tới \(N\).

Input

• Gồm một dòng duy nhất chứa số nguyên \(N\) (\(N \leq 10^6)\).

Output

• Xuất ra tất cả các số nguyên tố từ \(1\) tới \(N\) trên cùng một dòng và cách nhau một dấu cách.

Example

10

2 3 5 7