Bài tập

Trong buổi huấn luyện hôm nay, các bạn sẽ được thử thách với một bài toán cổ điển nhưng đòi hỏi tư duy phân tích sâu sắc. Giả sử chúng ta có một dãy số nguyên dương \(a\) gồm \(n\) phần tử, được đánh số từ \(1\) đến \(n\). Dãy số này tượng trưng cho các "mốc" năng lượng trên một đường đua thuật toán.

Để đánh giá khả năng xử lý truy vấn và tối ưu hóa, giảng viên đưa ra \(q\) truy vấn. Mỗi truy vấn có dạng \((l, r, d)\), yêu cầu các bạn đếm xem có bao nhiêu đoạn con nằm hoàn toàn trong đoạn từ \(l\) đến \(r\) có ước chung lớn nhất (GCD) không vượt quá \(d\).

Nói cách khác, với mỗi truy vấn, các bạn cần tìm số cặp chỉ số \((u, v)\) sao cho:

• \(l \le u \le v \le r\).
• \(\text{gcd}(a_u, a_{u+1}, \dots, a_v) \le d\).

Input

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(q\) (\(1 \le n, q \le 2 \cdot 10^5\)).
• Dòng thứ hai chứa \(n\) số nguyên dương \(a_1, a_2, \ldots, a_n\) (\(a_i \le 10^9\)).
• \(q\) dòng tiếp theo, mỗi dòng chứa ba số \(l, r, d\).

Output

• Với mỗi truy vấn, in kết quả ra trên một dòng.

Example

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

12
4
12
9
6

Scoring

• \(20\%\) số test có \(n, q \le 100\).
• \(30\%\) số test có \(n, q \le 1000\).
• \(30\%\) số test có \(d\) là hằng số, \(n, q \le 100000\).
• \(20\%\) số test còn lại không có ràng buộc gì thêm.

Tối qua tại thị trấn Mana xảy ra một vụ án nghiêm trọng. Cảnh sát lập tức tiến hành một cuộc điều tra và hiện xác định và tạm giam được \(N\) nghi phạm được đánh số từ 1 đến \(N\). Vừa thời gian diễn ra vào buổi tối nên lúc đấy chỉ có một nhân chứng đi qua và anh ta cũng không thể nhìn được mặt của thủ phạm. Nhân chứng chỉ nhìn được vóng dáng và biết được chiều cao của thủ phạm. Bây giờ nhân chứng sẽ tiến hành xác nhận xem ai là thủ phạm thật sự. Vì tình hình rất hỗn loạn nên phía cảnh sát chỉ có thể ước lượng rằng nghi phạm thứ \(i\) có chiều cao trong khoảng từ \(l_i\) đến \(r_i\). Để giúp nhân chứng nhận diện dễ dàng, cảnh sát sẽ phân các nghi phạm vào trong các phòng. Mỗi phòng sẽ gồm những nghi phạm được đánh số liên tiếp và không có 2 nghi phạm nào có cùng chiều cao (nghĩa là không tồn tại 2 nghi phạm \(i,j\) ở cùng chung phòng mà \([l_i,r_i ] \cap [l_j,r_j] \neq \emptyset\)).

Vì số lượng phòng không có quá nhiều nên đội trưởng đội điều tra hiện đang quan tâm đến câu hỏi rằng: Nếu tội phạm thật sự có chỉ số nằm trong khoảng từ \(a\) đến \(b\) thì số phòng tối thiểu cần sử dụng để điều tra là bao nhiêu.

Yêu cầu: Bạn hãy giúp đội trưởng đội điều tra trả lời \(Q\) câu hỏi như vậy.

Input

• Dòng đầu tiên chứa số nguyên dương \(N\) \((N\leq 200000)\) là số nghi phạm.

• Mỗi dòng trong số \(N\) dòng tiếp theo chứa 2 số nguyên dương \(l_i,r_i (l_i\leq r_i\leq 10^9)\) là phạm vi chiều cao của nghi phạm thứ \(i\).

• Dòng tiếp theo chứa số nguyên dương \(Q\) \((Q\leq 200000)\) là số câu hỏi.

• Mỗi dòng trong số \(Q\) dòng tiếp theo gồm 2 số nguyên dương \(a,b (a\leq b \leq N)\).

Output

• Đối với mỗi câu hỏi, hãy in ra số phòng tối thiểu phải sử dụng.

Example

2
1 1
1 1
3
1 1
2 2
1 2

1
1
2

3
1 1
2 2
3 3
3
1 1
2 3
1 3

1
1
1

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

3
1
3

Scoring

• Subtask \(1\) \((15\%)\): \(Q=1,a=1,b=N\).

• Subtask \(2\) \((25\%)\): \(N,Q \leq 5000\).

• Subtask \(3\) \((20\%)\): \(N\leq 5000,Q\leq 200000\).

• Subtask \(4\) \((20\%)\): \(N \leq 200000,Q\leq 100\).

• Subtask \(5\) \((20\%)\): Không có giới hạn gì thêm.

Cho dãy số nguyên \(a = a_{1}, a_{2},... , a_{n}\) và \(q\) truy vấn. Mỗi truy vấn có dạng \((L, R, x)\), cần tìm \(i\) sao cho \(L ≤ i ≤ R\) và \(a_{i} ∧ x\) đạt giá trị lớn nhất. Các số \(a_{i}\) và \(x\) đều được cho dưới dạng dãy nhị phân.

Input

• Dòng đầu tiên chứa hai số nguyên dương \(n\) và \(q\);

• Dòng thứ \(i\) trong \(n\) dòng tiếp theo chứa số \(a_{i}\) ở dạng nhị phân;

• \(q\) dòng tiếp theo, mỗi dòng chứa \((L, R, x)\) trong đó \(x\) ở dạng nhị phân

Output

Với mỗi truy vấn, in ra kết quả trên một dòng. Nếu có nhiều \(i\) thỏa mãn \(a_{i} ∧ x\) đạt giá trị lớn nhất thì in ra \(i\) nhỏ nhất có thể.

Example

5 4
100
101
1
1011
11
2 3 10
1 5 1100
3 5 1010
1 5 11100

2
5
3
5

Scoring

• Trong tất cả các test: \(n\), \(q ≤ 10^5\); tổng độ dài tất cả các xâu \(a_{i}\) không quá \(10^6\); tổng độ dài tất cả các xâu \(x\) không quá \(10^6\);

• Có \(8\%\) số test với \(n, q ≤ 5000\); độ dài các xâu nhị phân đều không quá \(30\);

• Có \(12\%\) số test với \(n, q ≤ 5000\);

• Có \(28\%\) số test với độ dài các xâu nhị phân đều không quá \(30\);

• Có \(52\%\) số test với ràng buộc gốc.

Xét \(x = (x_{1}, x_{2}, . . . , x_{m})\) là một dãy số. Phép dịch trái là chuyển phần tử đầu của dãy xuống cuối dãy. Dãy \(x\) sau khi thực hiện dịch trái \(k\) lần là \((x_{k+1}, x_{k+2}, . . . , x_{m}, x_{1}, x_{2}, . . . , x_{k})\). Dãy \(x\) được gọi là shlgood nếu \(m\) chẵn và có thể dịch trái một số lần (có thể là \(0\) lần) sao cho \(\frac{m}{2}\) phần tử đầu của dãy lớn hơn hẳn \(\frac{m}{2}\) phần tử cuối của dãy, tính từ trái sang phải. Cụ thể, dãy \(x\) là shlgood nếu tồn tại số nguyên không âm \(k\) sao cho sau khi dãy \(x\) dịch trái \(k\) lần, ta thu được dãy \(y\) thoả mãn \(y_{i} > y_{j}\) \(∀1 ≤ i ≤ \frac{m}{2} < j ≤ m\).

Cho dãy số nguyên \(a = (a_{1}, a_{2}, . . . , a_{n})\), hãy đếm số dãy con liên tiếp của a là dãy shlgood.

Input

• Dòng đầu tiên chứa số nguyên dương: \(n\);

• Dòng tiếp theo chứa \(n\) số nguyên: \(a_{1}, a_{2}, . . . , a_{n}\)

Output

Ghi một số nguyên duy nhất là số dãy con liên tiếp là dãy shlgood của \(a\).

Example

6
1 3 2 6 4 5

7

Scoring

• Trong tất cả các test: \(1 ≤ n ≤ 5 × 10^5, −10^9 ≤ a_{i} ≤ 10^9\).

• Có \(12\%\) số test với \(n ≤ 500\);

• Có \(24\%\) số test với \(n ≤ 5000\);

• Có \(20\%\) số test với \(a_{i}\) đôi một phân biệt;

• Có \(44\%\) số test với ràng buộc gốc.