It has been noted that if some ants are put in the junctions of the graphene integer lattice then they will act in the following fashion: every minute at each junction (x, y) containing at least four ants a group of four ants will be formed, and these four ants will scatter to the neighbouring junctions (x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1) — one ant in each direction. No other ant movements will happen. Ants never interfere with each other.

Scientists have put a colony of n ants into the junction (0, 0) and now they wish to know how many ants will there be at some given junctions, when the movement of the ants stops.

Input

First input line contains integers n (0 ≤ n ≤ 30000) and t (1 ≤ t ≤ 50000), where n is the number of ants in the colony and t is the number of queries. Each of the next t lines contains coordinates of a query junction: integers xi, yi ( - 109 ≤ xi, yi ≤ 109). Queries may coincide.

It is guaranteed that there will be a certain moment of time when no possible movements can happen (in other words, the process will eventually end).

Output

Print t integers, one per line — the number of ants at the corresponding junctions when the movement of the ants stops.

Examples

Input

1 3
0 1
0 0
0 -1


Output

0
1
0


Input

6 5
0 -2
0 -1
0 0
0 1
0 2


Output

0
1
2
1
0

Note

In the first sample the colony consists of the one ant, so nothing happens at all.

In the second sample the colony consists of 6 ants. At the first minute 4 ants scatter from (0, 0) to the neighbouring junctions. After that the process stops.
import java.io.BufferedInputStream;
import java.io.IOException;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashSet;
import java.util.InputMismatchException;
import java.util.Set;
import java.util.TreeSet;

public class Main
{
	private final int SIZEN = 100;
	private int[][] map = new int[2 * SIZEN + 1][2 * SIZEN + 1];
	
	public void dfs(int x, int y)
	{
		if(map[y][x] < 4)
		{
			return;
		}
		int m = map[y][x] / 4;
		map[y][x] %= 4;
		map[y][x - 1] += m;
		dfs(x - 1, y);
		map[y][x + 1] += m;
		dfs(x + 1, y);
		map[y - 1][x] += m;
		dfs(x, y - 1);
		map[y + 1][x] += m;
		dfs(x, y + 1);
	}
	
	public void foo()
	{
		MyScanner scan = new MyScanner();
		int n = scan.nextInt();
		map[SIZEN][SIZEN] = n;
		dfs(SIZEN, SIZEN);
		int t = scan.nextInt();
		for(int i = 0;i < t;++i)
		{
			int x = scan.nextInt();
			int y = scan.nextInt();
			if(x < -SIZEN || x > SIZEN || y < -SIZEN || y > SIZEN)
			{
				System.out.println(0);
			}
			else
			{
				System.out.println(map[y + SIZEN][x + SIZEN]);
			}
		}
	}
	
	public static void main(String[] args)
	{
		new Main().foo();
	}
	
	class Point implements Comparable<Point>
	{
		private int x;
		private int y;
		private int num;
		public Point(int aX, int aY, int aNum)
		{
			x = aX;
			y = aY;
			num = aNum;
		}
		public int compareTo(Point p)
		{
			return p.num - num;
		}
	}
	
	class MyScanner
	{
	    private byte[] buf = new byte[1024];
	    private int curChar;
	    private int numChars;
	    BufferedInputStream bis = new BufferedInputStream(System.in);

	    public int read() 
	    {
	        if (-1 == numChars)
	        {
	        	throw new InputMismatchException();
	        }
	        if (curChar >= numChars)
	        {
	            curChar = 0;
	            try 
	            {
	                numChars = bis.read(buf);
	            }
	            catch (IOException e)
	            {
	                throw new InputMismatchException();
	            }
	            if (numChars <= 0)
	            {
	            	return -1;
	            }
	        }
	        return buf[curChar++];
	    }

	    public int nextInt() 
	    {
	        int c = read();
	        while (isSpaceChar(c))
	        {
	        	c = read();
	        }
	        int sgn = 1;
	        if (c == '-') 
	        {
	            sgn = -1;
	            c = read();
	        }
	        int res = 0;
	        do 
	        {
	            if (c < '0' || c > '9')
	            {
	            	throw new InputMismatchException();
	            }
	            res *= 10;
	            res += c - '0';
	            c = read();
	        } while (!isSpaceChar(c));
	        return res * sgn;
	    }
	    
	    public long nextLong() 
	    {
	    	int c = read();
	    	while (isSpaceChar(c))
	    	{
	    		c = read();
	    	}
	    	int sgn = 1;
	    	if (c == '-') 
	    	{
	    		sgn = -1;
	    		c = read();
	    	}
	    	long res = 0;
	    	do 
	    	{
	    		if (c < '0' || c > '9')
	    		{
	    			throw new InputMismatchException();
	    		}
	    		res *= 10;
	    		res += c - '0';
	    		c = read();
	    	} while (!isSpaceChar(c));
	    	return res * sgn;
	    }
	    
	    public String next()
	    {
	        int c = read();
	        while (isSpaceChar(c))
	        {
	        	c = read();
	        }
	        StringBuilder res = new StringBuilder();
	        do 
	        {
	            res.appendCodePoint(c);
	            c = read();
	        } while (!isSpaceChar(c));
	        return res.toString();
	    }

	    private boolean isSpaceChar(int c) 
	    {
	        return ' ' == c || '\n' == c || '\r' == c || '\t' == c || -1 == c;
	    }
	}
}