Độ khó: Khá (3/4 điểm)

Lưu ý: Tuy đề bài yêu cầu dữ liệu với file nhưng trên web thì cứ mặc định là đọc từ bàn phím và in ra màn hình nha các bạn

Cho dãy số nguyên ~A~ gồm ~n~ số nguyên: ~a_1, a_2, \dots, a_n~.

Một đoạn con gồm các phần tử liên tiếp của ~A~ từ vị trí ~s~ đến vị trí ~t~ (~s \le t~) được gọi là đoạn con đặc biệt nếu thỏa mãn điều kiện:

~a_s \cdot a_{s+1} \cdot \dots \cdot a_t = \operatorname{lcm}(a_s, a_{s+1}, \dots, a_t)~

với ~\operatorname{lcm}(a_s, a_{s+1}, \dots, a_t)~ là bội chung nhỏ nhất của ~a_s, a_{s+1}, \dots, a_t~.

Có ~q~ truy vấn, truy vấn thứ ~i~ là: cho hai số nguyên ~l_i~ và ~r_i~, hãy chia đoạn ~a_{l_i}, a_{l_i+1}, \dots, a_{r_i}~ thành ít nhất các đoạn con đặc biệt.

Yêu cầu: Với mỗi truy vấn, hãy tìm số đoạn con đặc biệt ít nhất.

Input

• Dòng thứ nhất chứa hai số nguyên dương ~n~ và ~q~ (~1 \le n, q \le 10^5~);
• Dòng thứ hai chứa ~n~ số nguyên dương ~a_1, a_2, \dots, a_n~ (~1 \le a_i \le 10^5~);
• ~q~ dòng tiếp theo, dòng thứ ~i~ chứa hai số nguyên ~l_i~ và ~r_i~ (~1 \le l_i \le r_i \le n~).

Output

Gồm ~q~ dòng, dòng thứ ~i~ ghi kết quả của truy vấn thứ ~i~.

Scoring

Sample Input 1

5 2
2 3 10 7 5
2 4
3 5

Sample Output 1

1
2

Notes

Truy vấn 1: các phần tử ~3, 10, 7~ có tích và bội chung nhỏ nhất cùng bằng ~210~, nên chia thành số đoạn con đặc biệt ít nhất là ~1~.

Truy vấn 2: các phần tử ~10, 7, 5~ có thể chia thành ít nhất ~2~ đoạn con đặc biệt thỏa mãn.

Độ khó: Khó (4/4 điểm)

Lưu ý: Tuy đề bài yêu cầu dữ liệu với file nhưng trên web thì cứ mặc định là đọc từ bàn phím và in ra màn hình nha các bạn

Alice thiết kế một trò chơi trên một lưới vuông kích thước ~n \times n~. Các hàng được đánh số từ ~1~ đến ~n~ từ trên xuống dưới, các cột được đánh số từ ~1~ đến ~n~ từ trái sang phải. Ô ~(i,j)~ là ô giao giữa hàng ~i~ (~1 \le i \le n~) và cột ~j~ (~1 \le j \le n~). Nhân vật chính của trò chơi là một chú ếch đang ở ô ~(x,y)~ và cần nhảy về một trong bốn ô góc ~(1,1)~, ~(1,n)~, ~(n,1)~, ~(n,n)~ của lưới vuông.

Để trò chơi thêm hấp dẫn Alice đã thiết kế thêm ~k~ ô phát sáng trên lưới. Người chơi cần tìm cách điều khiển chú ếch để mất ít sức lực nhất theo quy tắc:

• Nhảy sang ô không phát sáng chung cạnh mất ~1~ đơn vị sức lực;
• Nếu có ô phát sáng cùng hàng hoặc cùng cột với ô hiện tại của chú ếch thì chú ếch có thể nhảy tới ô đó mà không mất sức lực nào.

Yêu cầu: Tìm cách nhảy để chú ếch mất tổng sức lực là nhỏ nhất.

Input

• Dòng thứ nhất chứa bốn số nguyên dương ~n, k, x, y~ (~1 \le x, y \le n~);
• Dòng thứ ~t~ (~1 \le t \le k~) trong ~k~ dòng sau chứa hai số ~u_t, v_t~ (~1 \le u_t, v_t \le n~) cho biết ô ~(u_t,v_t)~ phát sáng.

Output

Một số nguyên duy nhất theo yêu cầu bài toán.

Scoring

Sample Input 1

5 2 4 3
1 4
4 1

Sample Output 1

1

Sample Input 2

5 1 4 2
1 4

Sample Output 2

2

Độ khó: Khó (4/4 điểm)

Lưu ý: Tuy đề bài yêu cầu dữ liệu với file nhưng trên web thì cứ mặc định là đọc từ bàn phím và in ra màn hình nha các bạn

Thành phố ~Z~ gồm ~n~ địa điểm khác nhau, được đánh số từ ~1~ đến ~n~ và có ~m~ tuyến đường hai chiều nối giữa các địa điểm này, hai địa điểm bất kỳ có duy nhất một tuyến đường. Hiện nay, cảnh sát đang tìm kiếm nơi trú ẩn của một tên tội phạm ở trong các địa điểm của thành phố.

Theo thông tin từ người dân, cảnh sát biết được tên tội phạm đã di chuyển từ một địa điểm ~x~ đến nơi trú ẩn là địa điểm ~y~. Các nhân chứng có trông thấy tên tội phạm này xuất hiện ở ~k~ địa điểm ~u_1, u_2, \dots, u_k~ trên đường đi từ ~x~ đến ~y~ theo thứ tự bất kỳ mà cảnh sát chưa xác định. Lưu ý rằng tên tội phạm có thể di chuyển từ ~x~ đến ~y~ thông qua các địa điểm khác không có trong ~k~ địa điểm mà các nhân chứng trông thấy.

Qua phân tích đặc điểm của tên tội phạm, cảnh sát đã xác định được tên tội phạm di chuyển theo đường đi ngắn nhất từ ~x~ đến ~y~. Lời khai của các nhân chứng có thể không đồng nhất dẫn đến không tìm thấy một địa điểm ~y~ nào thỏa mãn.

Yêu cầu: Hãy tìm các địa điểm có thể là ~y~ để giúp cảnh sát tìm được tên tội phạm.

Input

• Dòng thứ nhất chứa ba số nguyên ~n, m, k~ (~1 \le k \le n \le 2 \cdot 10^5~; ~1 \le m \le 2 \cdot 10^5~);
• Dòng thứ hai chứa ~k~ số nguyên ~u_i~ mô tả những địa điểm tên tội phạm xuất hiện (~1 \le u_i \le n~);
• ~m~ dòng tiếp theo, mỗi dòng chứa ba số nguyên ~a, b, c~ cho biết tuyến đường nối hai địa điểm ~a~ và ~b~ có độ dài là ~c~ (~1 \le a \ne b \le n~, ~1 \le c \le 10^9~).

Output

• Dòng thứ nhất ghi ra ~p~ là số địa điểm có thể là ~y~;
• Dòng thứ hai ghi ra ~p~ số nguyên là những địa điểm có thể là ~y~ theo thứ tự giá trị tăng dần.

Ghi chú: Trong trường hợp không tìm thấy điểm có thể là ~y~ thì ghi ra số ~0~ duy nhất.

Scoring

Sample Input 1

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

Sample Output 1

4
1 2 4 5