Petya and Vasya are inventing a new game that requires a rectangular board and one chess piece. At the beginning of the game the piece stands in the upper-left corner of the board. Two players move the piece in turns. Each turn the chess piece can be moved either one square to the right or one square down or jump k squares diagonally down and to the right. The player who can’t move the piece loses. 

<image>

The guys haven’t yet thought what to call the game or the best size of the board for it. Your task is to write a program that can determine the outcome of the game depending on the board size.

Input

The first input line contains two integers t and k (1 ≤ t ≤ 20, 1 ≤ k ≤ 109). Each of the following t lines contains two numbers n, m — the board’s length and width (1 ≤ n, m ≤ 109).

Output

Output t lines that can determine the outcomes of the game on every board. Write «+» if the first player is a winner, and «-» otherwise.

Examples

Input

10 2
1 1
1 2
2 1
2 2
1 3
2 3
3 1
3 2
3 3
4 3


Output

-
+
+
-
-
+
-
+
+
+
import java.io.*;
import java.util.*;

import static java.lang.Math.*;
import static java.util.Arrays.fill;
import static java.util.Arrays.binarySearch;
import static java.util.Arrays.sort;

public class Main {

	public static void main(String[] args) throws IOException {
		new Thread(null, new Runnable() {
			public void run() {
				try {
					new Main().run();
				} catch (IOException e) {
					e.printStackTrace();
				}
			}
		}, "1", 1 << 24).start(); 
	}

	BufferedReader in;
	PrintWriter out;
	StringTokenizer st = new StringTokenizer("");
	
	int T;
	int N;
	int M;
	int K = 1;
	int[][] used = new int [1000][1000];
	boolean[][] dp = new boolean [1000][1000];
	int tick = 1;
	
	void run() throws IOException {
		in = new BufferedReader(new FileReader("input.txt"));
		out = new PrintWriter("output.txt");
		T = nextInt();
		K = nextInt();
		while (T --> 0)
			out.println(solve(nextInt() - 1, nextInt() - 1) ? '+' : '-');
		out.close();
	}
	
	void print(int n, int m, int k) {
		N = n;
		M = m;
		K = k;
		tick++;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++)
				out.print(dfs(n - i - 1, m - j - 1) ? '#' : ' ');
			out.println();
		}
//		System.out.println(solve(n - 1, m - 1));
	}

	boolean dfs(int n, int m) {
		if (used[n][m] == tick)
			return dp[n][m];
		boolean ret = false;
		if (n > 0)
			ret |= !dfs(n - 1, m);
		if (m > 0)
			ret |= !dfs(n, m - 1);
		if (n >= K && m >= K)
			ret |= !dfs(n - K, m - K);
		used[n][m] = tick;
		return dp[n][m] = ret;
	}
	
	boolean solve(int n, int m) {
		if (K == 1)
			return (n & 1) == 1 || (m & 1) == 1;
		int x = min(n / (K + 1), m / (K + 1));
//		System.out.println(x);
		if (K > min(n, m))
			return ((n + m) & 1) == 1;
		int y = min(n + 1, m + 1);
		if (y % (K + 1) == 0 && y > K)
			return true;
		boolean invert = x % 2 == 1;
		boolean ret = ((n + m) & 1) == 1;
		return invert ? !ret : ret;
	}
	
	String nextToken() throws IOException {
		while (!st.hasMoreTokens())
			st = new StringTokenizer(in.readLine());
		return st.nextToken();
	}
	
	int nextInt() throws IOException {
		return Integer.parseInt(nextToken());
	}
	
	long nextLong() throws IOException {
		return Long.parseLong(nextToken());
	}
	
	double nextDouble() throws IOException {
		return Double.parseDouble(nextToken());
	}
	
	String nextLine() throws IOException {
		st = new StringTokenizer("");
		return in.readLine();
	}
	
	boolean EOF() throws IOException {
		while (!st.hasMoreTokens()) {
			String s = in.readLine();
			if (s == null)
				return true;
			st = new StringTokenizer(s);
		}
		return false;
	}
}
