Firdavs is living on planet F. There are $N$ cities (numbered $1$ through $N$) on this planet; let's denote the value of city $i$ by $v_i$. Firdavs can travel directly from each city to any other city. When he travels directly from city $x$ to city $y$, he needs to pay $f(x, y) = |v_y-v_x|+y-x$ coins (this number can be negative, in which case he receives $-f(x, y)$ coins).
Let's define a simple path from city $x$ to city $y$ with length $k \ge 1$ as a sequence of cities $a_1, a_2, \ldots, a_k$ such that all cities in this sequence are different, $a_1 = x$ and $a_k = y$. The cost of such a path is $\sum_{i=1}^{k-1} f(a_i, a_{i+1})$.
You need to answer some queries for Firdavs. In each query, you are given two cities $x$ and $y$, and you need to find the minimum cost of a simple path from city $x$ to city $y$. Then, you need to find the length of the longest simple path from $x$ to $y$ with this cost.

-----Input-----
- The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
- The first line of each test case contains two space-separated integers $N$ and $Q$.
- The second line contains $N$ space-separated integers $v_1, v_2, \ldots, v_N$.
- The following $Q$ lines describe queries. Each of these lines contains two space-separated integers $x$ and $y$.

-----Output-----
For each query, print a single line containing two space-separated integers ― the minimum cost and the maximum length.

-----Constraints-----
- $1 \le T \le 100$
- $1 \le N, Q \le 2 \cdot 10^5$
- $0 \le v_i \le 10^9$ for each valid $i$
- $1 \le x, y \le N$
- the sum of $N$ in all test cases does not exceed $5 \cdot 10^5$
- the sum of $Q$ in all test cases does not exceed $5 \cdot 10^5$

-----Subtasks-----
Subtask #1 (30 points):
- $1 \le N, Q \le 1,000$
- $v_1 < v_2 < \ldots < v_N$
- the sum of $N$ in all test cases does not exceed $5,000$
- the sum of $Q$ in all test cases does not exceed $5,000$
Subtask #2 (70 points): original constraints

-----Example Input-----
2
4 2
4 2 5 7
2 3
3 4
2 1
1 1
2 1

-----Example Output-----
4 3
3 2
-1 2

-----Explanation-----
Example case 1: For the first query, there are two paths with cost $4$ from city $2$ to city $3$:
- $2 \rightarrow 1 \rightarrow 3$: cost $(|4-2|+1-2)+(|5-4|+3-1) = 4$, length $3$
- $2 \rightarrow 3$: cost $|5-2|+3-2 = 4$, length $2$
All other paths have greater costs, so the minimum cost is $4$. Among these two paths, we want the one with greater length, which is $3$.

Difficulty: interview

Starter code:

Solutions:
# cook your dish here
import bisect
for _ in range(int(input())):
 N,Q=list(map(int,input().strip().split(' ')))
 V=list(map(int,input().strip().split(' ')))
 VV=sorted(V)
 for ___ in range(Q):
  x,y=list(map(int,input().strip().split(' ')))
  x-=1
  y-=1
  ans1=abs(V[x]-V[y])+(y-x)
  post1=bisect.bisect_left(VV,min(V[x],V[y]))
  post2=bisect.bisect_right(VV,max(V[x],V[y]))
  ans2=post2-post1
  print(ans1,ans2)


T=int(input())
for i in range(0,T):
 N,Q=map(int,input().split())
 s=[int(x) for x in input().split()]
 L=sorted(s)
 G=L[::-1]
 for j in range(0,Q):
  x,y=map(int,input().split())
  ans1=abs(s[y-1]-s[x-1])+y-x
  print(ans1,end=" ")

  pos1=0
  pos2=N

  for k in range(0,len(L)):
   if(L[k]<min(s[x-1],s[y-1])):
    pos1=k
   elif(L[k]==min(s[x-1],s[y-1])):
    pos1=k
    break
   else:
    break

  for k in range(0,len(L)):
   if(G[k]>max(s[x-1],s[y-1])):
    pos2=N-k-1
   elif(G[k]==max(s[x-1],s[y-1])):
    pos2=N-k-1
    break
   else:
    break

  print(pos2-pos1+1)
  


for _ in range(int(input())):
 n,q = [int(a) for a in input().split()]
 v = list(map(int, input().split()))
 s = list(range(1, n+1))
 index_s = [x for _,x in sorted(zip(v,s))]
 sorted_v = sorted(v)
 #print(index_s)
 #print(sorted_v)
 for i in range(q):
  x,y = [int(a) for a in input().split()]
  check1 = min(x,y)
  get_index1 = index_s.index(check1)
  vx = sorted_v[get_index1]


  check2 = max(x,y)
  get_index2 = index_s.index(max(x,y))
  vy = sorted_v[get_index2]

  length = get_index2-get_index1 + 1
  ans = vy-vx+y-x
  print(ans, length)






import bisect

for _ in range(int(input())):
 n, q = list(map(int, input().split()))
 ar = list(map(int, input().split()))

 new = ar.copy()
 new.sort()

 for __ in range(q):
  x, y = list(map(int, input().split()))
  cost = abs(ar[y - 1] - ar[x - 1]) + y - x

  length = bisect.bisect_right(new, max(ar[y - 1], ar[x - 1]))
  length -= bisect.bisect_left(new, min(ar[x - 1], ar[y - 1]))

  print(cost, length)


t = int(input())
for i in range(t):
 n, q = input().split()
 cities = [int(x) for x in input().split()]
 cities_sort = cities.copy()
 cities_sort.sort()
 for j in range(int(q)):
  q1, q2 = [int(x) for x in input().split()]
  a = cities[q1 - 1]
  b = cities[q2 - 1]
  if (a > b):
   c = a
   a = b
   b = c
  pos_a = cities_sort[::1].index(a)
  pos_b = len(cities_sort) - 1 - cities_sort[::-1].index(b)
  print(q2 - q1 + b - a, pos_b - pos_a + 1)

t = int(input())
for i in range(t):
 n, q = list(map(int,input().split()))
 cities = list(map(int,input().split()))
 for j in range(int(q)):
  q1, q2 = list(map(int,input().split()))
  a = cities[q1 - 1]
  b = cities[q2 - 1]
  if (a > b):
   c = a 
   a = b
   b = c
  size = 0
  for c in cities:
   if c >= a and c <= b:
    size += 1
  print(q2 - q1 + b - a, size)

t=int(input())
for _ in range(t):
 n,q=list(map(int,input().split()))
 v=list(map(int,input().split()))
 vv=v[:]
 vv=[[j,i] for j,i in enumerate(v)]
 vv.sort(key=lambda x:x[1])
 vvv=[]
 for jj,i in enumerate(vv):
  v[i[0]]=[jj,i[1]]
 #print(v)
 for i in range(q):
  x,y=list(map(int,input().split()))
  x-=1
  y-=1
  xx=v[x][0]
  yy=v[y][0]
  # print(vv[xx:yy+1])
  # print('a',xx,yy)
  if xx<yy:
   le=yy-xx+1
   cost=v[y][1]-v[x][1]
   cost+=(y-x)
   # cost-=1
  elif xx==yy:
   le=1
   cost=0
  else:
   le=xx-yy+1
   cost=v[x][1]-v[y][1]
   cost-=(x-y)
   # cost+=1
   
  print(cost,le)