문제

쌍의 커플이 있는 나라에 홀로 솔로로 살고 있는 시아는, 갑자기 다음과 같은 궁금증이 들었다.

'각 커플에 번부터 번까지 번호를 매겨 i번 커플을 한 명의 위치 , 다른 한 명의 위치 , 둘이 서로 만나지 못 할 때의 불안도 로 나타낸다면, 위치가 보다 크거나 같고, 보다 작거나 같은 모든 사람을 다른 차원으로 이동시킬 때 쌍의 커플들에 대한 불안도의 합의 최댓값은 어떻게 될까?'

이때, 둘이 같은 차원에 위치하는 커플은 서로 만날 수 있다고 한다.

시아는 위 궁금증을 해결하기 위해 계산을 무척 잘하는 당신에게 번의 질문을 하기로 결심했다. 각 질문의 내용은 다음과 같다.

: 위치가 보다 크거나 같고, 보다 작거나 같은 모든 사람을 다른 차원으로 이동시켰다고 가정했을 때 쌍의 커플들에 대한 불안도의 합

시아를 위해 번의 질문에 대한 각각의 답을 구해 시아에게 알려주자!

입력

첫 번째 줄에 커플의 수 과 질문의 수 가 공백으로 구분되어 주어진다.

두 번째 줄부터 개의 줄에 걸쳐, 번 줄에 번 커플의 정보 가 공백으로 구분되어 주어진다.

번째 줄부터 개의 줄에 걸쳐, 번 줄에 번째 질문의 내용 가 공백으로 구분되어 주어진다.

제한

주어지는 모든 수는 정수이다.

출력

첫 번째 줄부터 개의 줄에 걸쳐, 번 줄에 번째 질문에 대한 답을 출력한다.