Gretchen and Strange Function

Labib666 The Tough Summer Spar 201...
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.

Sample

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

Submit

Login to submit.

Statistics

60% Solution Ratio
nfssdqEarliest, Jul '16
AungkurFastest, 0.2s
khatribiruLightest, 5.1 MB
bqi343Shortest, 692B
Toph uses cookies. By continuing you agree to our Cookie Policy.