Một dãy số nguyên có \(k\) phần tử \(a_1,a_2,...,a_k\) được gọi là dãy nai-sừ khi \(k=1\) hoặc nó là một dãy số nguyên liên tiếp, hay: \(a_{i}+1=a_{i+1}(1\le i<k)\)
Cho một dãy số nguyên \(a\) có \(n\) phần tử và một số nguyên dương \(k\). Trong một thao tác, ta có thể chọn một phần tử \(a_i\) và tăng hoặc giảm phần tử đó đi \(1\) đơn vị. Một cách chia đoạn của dãy \(a\) được gọi là nai-sừ khi:

• Mỗi phần tử của dãy \(a\) thuộc vào đúng một đoạn
• Gọi chi phí của một đoạn là số lần thao tác ít nhất để đưa đoạn đó trở thành dãy nai-sừ thì mọi chi phí của các đoạn được chia đều không vượt quá \(k\)
• Số đoạn được chia là ít nhất có thể

Có \(q\) truy vấn, mỗi truy vấn cho hai số nguyên dương \(l,r(1\le l\le r\le n)\), bạn cần trả lời số đoạn được chia trong cách chia đoạn nai-sừ của dãy con liên tiếp \(a_l,a_{l+1},...,a_r\)

Input

• Dòng \(1\) chứa ba số nguyên dương \(n,k,q(1\le n,q\le 10^5, 1\le k\le 10^{16})\)
• Dòng \(2\) chứa \(n\) số nguyên \(a_1,a_2,...,a_n(|a_i|\le 10^9 \forall i\in [1;n])\)
• \(q\) dòng tiếp theo, mỗi dòng có hai số nguyên dương \(l,r(1\le l\le r\le n)\)

Output

• Gồm \(q\) dòng, dòng thứ \(i\) chứa một số nguyên dương duy nhất là đáp án cho truy vấn thứ \(i\)

Scoring

• Subtask \(1\) (\(10\)% số điểm): \(n,q\le 10\)
• Subtask \(2\)(\(15\)% số điểm): \(q=1,n\le 1000\)
• Subtask \(3\)(\(15\)% số điểm): \(q=1,n\le 10^5\)
• Subtask \(4\)(\(20\)% số điểm):\(n,q\le 1000\)
• Subtask \(5\)(\(40\)% số điểm): Không có ràng buộc gì thêm

Example

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

3
3
2

Note

• Truy vấn \(1\), chia dãy thành các đoạn như sau: \([2,4,8][4,7,10][4,6]\)
• Truy vấn \(2\), chia dãy thành các đoạn như sau: \([8][4,7,10][4]\)
• Truy vấn \(3\), chia dãy thành các đoạn như sau: \([5,8][4,7]\)