Practice on Toph

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

Gretchen and Strange Function

Limits: 1s, 512 MB

Gretchen loves experimenting with functions. She came up with an interesting function recently that looks like the following:

int H-function ( int N, int A, int B, int C ) {

    if ( B > N ) return A;

    int curA = A;

    while ( true ) {
        int newA = curA + C * B;
        if ( newA < 1 || newA > N ) break;
        curA = newA;
    }

    return H-function ( N, curA, B+1, (-1)*C );

}

She wonders what values H-function will return for different values of the parameters. Since you are the smartest friend she has, she asked you to help her solve this problem.

Given the values of N, A, and B, tell her the return value of H-function ( N, A, B, 1 ).

Input

The first line of input contains two integers: T, N.
Here, T is the number of queries Gretchen will make.

Each of the next T lines contains two space-separated integers: A, B.

Constraints

1 <= T <= 3*105
1 <= N, A, B <= 104
A <= N
B <= N

Output

For each query, print the return value of H-function ( N, A, B, 1 ) on a new line.

Samples

InputOutput
2 3
1 1
1 2

1
3

####Explanation:

Let us look at the calls made to H-function in the first query:
H-function (3,1,1,1)
H-function (3,3,2,-1)
H-function (3,1,3,1)
H-function (3,1,4,-1) -> returns 1

Let us look at the calls made to H-function in the second query:
H-function (3,1,2,1)
H-function (3,3,3,-1)
H-function (3,3,4,1) -> returns 3

Author
  • Labib666's Avatar

    Labib666

    Labib loves to solve problems unless confronted with real life ones which he procrastinates upon with food and sitcoms.
Discussion
Submit

Login to submit