Farmer John이 3SUM을 푼다

Farmer John은 알고리즘 설계에서 큰 돌파구를 찾았다고 믿는다. 그는 3SUM 문제에 대해 거의 선형 시간에 동작하는 알고리즘을 찾았다고 주장한다. 3SUM 문제는 지금까지 알려진 해법 중 이차 시간보다 월등히 빠른 것이 없다는 점으로 유명하다. 3SUM 문제의 한 가지 형태는 다음과 같다. 정수 배열 $s\_1,\dots,s\_m$이 주어졌을 때, 서로 다른 인덱스 $i,j,k$의 순서 없는 삼중항 중 $s\_i + s\_j + s\_k = 0$을 만족하는 것의 개수를 세는 것이다.

Farmer John의 주장을 확인하기 위해 Bessie는 $N$개의 정수로 이루어진 배열 $A$를 준비했다 ($1 \leq N \leq 5000$). Bessie는 또한 $Q$개의 질의를 준다 ($1 \leq Q \leq 10^5$). 각 질의는 두 인덱스 $1 \leq a\_i \leq b\_i \leq N$으로 구성된다. 각 질의에 대해 Farmer John은 부분 배열 $A\[a\_i \dots b\_i]$에서 3SUM 문제를 풀어야 한다.

안타깝게도 Farmer John은 방금 자신의 알고리즘에 결함이 있음을 발견했다. 그는 알고리즘을 고칠 수 있다고 확신하지만, 그 동안 Bessie의 테스트를 통과할 수 있도록 당신에게 도움을 요청한다!

첫 번째 줄에는 공백으로 구분된 두 정수 $N$과 $Q$가 주어진다. 두 번째 줄에는 배열 $A$의 원소 $A\_1,\dots,A\_N$이 공백으로 구분되어 주어진다. 이후 $Q$개의 줄 각각에는 질의를 나타내는 두 정수 $a\_i$와 $b\_i$가 공백으로 구분되어 주어진다.

모든 배열 원소 $A\_i$에 대해 $-10^6 \leq A\_i \leq 10^6$이 보장된다.

출력은 $Q$개의 줄로 구성된다. 각 줄 $i$에는 $i$번째 질의의 답인 정수 하나를 출력한다. 오버플로를 피하기 위해 64비트 정수를 사용해야 한다.

첫 번째 질의에서 가능한 삼중항은 $(A\_1,A\_2,A\_5)$와 $(A\_2,A\_3,A\_4)$이다.