Server Time: Sat Feb 23, 2019 12:48 am
Welcome ( logout
1100 - Again Array Queries
  PDF (English) Statistics Forum
Time Limit: 3 second(s) Memory Limit: 32 MB

Given an array with n integers, and you are given two indices i and j (i ≠ j) in the array. You have to find two integers in the range whose difference is minimum. You have to print this value. The array is indexed from 0 to n-1.

Input

Input starts with an integer T (≤ 5), denoting the number of test cases.

Each case contains two integers n (2 ≤ n ≤ 105) and q (1 ≤ q ≤ 10000). The next line contains n space separated integers which form the array. These integers range in [1, 1000].

Each of the next q lines contains two integers i and j (0 ≤ i < j < n).

Output

For each test case, print the case number in a line. Then for each query, print the desired result.

Sample Input

Output for Sample Input

2

5 3

10 2 3 12 7

0 2

0 4

2 4

2 1

1 2

0 1

Case 1:

1

1

4

Case 2:

1

Notes

Dataset is huge, use faster I/O methods.


Special Thanks: Jane Alam Jan (Description, Solution, Dataset)
Developed and Maintained by
JANE ALAM JAN
Copyright © 2012
LightOJ, Jane Alam Jan