Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Red and Green

By dipto98 · Limits 500ms, 512 MB

Suppose, there is an array of N integers. Each index of the array is either red or green. The first index is red, then the following is green, then the very next one is again red, then green again and the pattern will be like this.

You are given m queries and each query contains p, q integers.Your task is to find out the number of red and green lie between the range p and q (inclusive).

Input

The first line of the input contains an integer T (T ≤ 50) indicates the testcase.Following T lines there will be two integers n (1 ≤ n ≤ 105), m (1 ≤ m ≤ 2x103) indicates the size of array and the number of query respectively. The index will be 1, 2… n. Then m lines follows two integers p, q (1 ≤ p ≤ q ≤ 105) respectively.

Output

For each query print two integers r and g, the total number of red and green in the range. There is a space between r and g and don’t forget to print new line after each query.

Sample

InputOutput
2
5 2
1 3
1 5
10  4
5 5
2 9
4 8
1 10
2 1
3 2
1 0
4 4
2 3
5 5


Discussion
Statistics

87% Solution Ratio

BruteforcekidEarliest, Jul '17

subhashis_cseFastest, 0.0s

SowmenLightest, 393 kB

mdvirusShortest, 252B

Submit

Login to submit