Cho một dãy số nguyên dương gồm N phần tử ~a_1, a_2, a_3, …, a_N~ và một số nguyên dương Q tương ứng với số lượng truy vấn.

Mỗi truy vấn có dạng L, R (~L≤ R ≤ N~). Với mỗi đoạn con (u, v) thuộc đoạn L, R (~L ≤ u ≤ v ≤ R~) tìm đoạn con có UCNN lớn nhất.

Yêu cầu:

Viết chương trình giải quyết Q truy vấn.

Dữ liệu: Từ tệp văn bản SUBGCD.INP.

• Dòng đầu tiên là 2 số nguyên dương N, Q. (~N, Q≤10^5~)

• Dòng tiếp theo gồm N số nguyên dương ~a_1, a_2, a_3, …, a_N~.(~a_i ≤ 10^6~)

• Q dòng tiếp theo mỗi dòng là 2 số nguyên L, R.

Kết quả: Ghi ra tệp văn bản SUBGCD.OUT Q dòng, mỗi dòng là UCNN lớn nhất tìm được.

Ví dụ: SUBGCD.INP

5 2
1 2 2 6 8
1 3
2 4

SUBGCD.OUT

2
6

Ràng buộc

Subtask 1: (30% số điểm) có N, Q≤500

Subtask 2: (40% số điểm) có N, Q≤5000

Subtask 3: (40% số điểm) có N, Q≤105 và ~|L_i – L_i-1|~ = 1 và |~R_i – R_i-1~| = 1

Cho một xâu kí tự S gồm các chữ cái in hoa và một số nguyên dương Q tương ứng với số lượng truy vấn. Mỗi truy vấn có dạng u, v (u, v là kí tự in hoa) thay thế tất cả các kí tự u trong S thành v.

Yêu cầu: Xâu S sau Q truy vấn

Dữ liệu: Từ tệp văn bản REPLACES.INP gồm:

• Dòng đầu tiên gồm xâu S ~(|S| ≤ 10^5)~ và số nguyên dương Q

• Q dòng tiếp theo mỗi dòng gồm 2 kí tự u và v.

Kết quả : Ghi ra tệp văn bản REPLACES.OUT

• Một dòng duy nhất là xâu S sau Q truy vấn

Ví dụ:

REPLACES.INP

ABABAC 4
C D
A C
B C
C B

REPLACES.OUT

BBBBBD

Ràng buộc:

Subtask 1: (40% số điểm) có |S|, Q≤5000

Subtask 2: (60% số điểm) có |S|, ~Q≤10^5~

Cho một dãy số nguyên dương gồm N phần tử ~a_1, a_2, a_3, …, a_N~. Đếm xem có bao nhiêu số có đúng 7 ước nguyên dương.

Yêu cầu: Số lượng các số có đúng 7 ước nguyên dương

Dữ liệu: Vào từ file văn bản SEVEN.INP:

• Dòng đầu tiên chứa số nguyên N (~1 ≤ N≤ 10^5~),

• Dòng tiếp theo gồm N số nguyên dương ~a_1, a_2, a_3, …, a_N~.(~a_i ≤ 10^1~~^8~)

Kết quả: Đưa ra file văn bản SEVEN.OUT:

• Một dòng duy nhất là yêu cầu của bài toán

Ví dụ:

SEVEN.INP

6
729 28 64 53 100 15625

SEVEN.OUT

3

Ràng buộc:

Subtask 1: (60% số điểm) có N ≤ ~10^4~, ~a_i ≤ 10^6~

Subtask 1: (40% số điểm) có N ≤ 10^5, ~a_i ≤ 10^1~~^8~