Problem: This is an interactive problem.

Omkar has just come across a duck! The duck is walking on a grid with n rows and n columns (2 ≤ n ≤ 25) so that the grid contains a total of n^2 cells. Let's denote by (x, y) the cell in the x-th row from the top and the y-th column from the left. Right now, the duck is at the cell (1, 1) (the cell in the top left corner) and would like to reach the cell (n, n) (the cell in the bottom right corner) by moving either down 1 cell or to the right 1 cell each second.

Since Omkar thinks ducks are fun, he wants to play a game with you based on the movement of the duck. First, for each cell (x, y) in the grid, you will tell Omkar a nonnegative integer a_{x,y} not exceeding 10^{16}, and Omkar will then put a_{x,y} uninteresting problems in the cell (x, y). After that, the duck will start their journey from (1, 1) to (n, n). For each cell (x, y) that the duck crosses during their journey (including the cells (1, 1) and (n, n)), the duck will eat the a_{x,y} uninteresting problems in that cell. Once the duck has completed their journey, Omkar will measure their mass to determine the total number k of uninteresting problems that the duck ate on their journey, and then tell you k.

Your challenge, given k, is to exactly reproduce the duck's path, i. e. to tell Omkar precisely which cells the duck crossed on their journey. To be sure of your mastery of this game, Omkar will have the duck complete q different journeys (1 ≤ q ≤ 10^3). Note that all journeys are independent: at the beginning of each journey, the cell (x, y) will still contain a_{x,y} uninteresting tasks.

Interaction

The interaction will begin with a line containing a single integer n (2 ≤ n ≤ 25), the amount of rows and columns in the grid. Read it.

Your program should then print n lines. The x-th line should contain n integers a_{x,1}, a_{x,2}, ..., a_{x,n} satisfying 0 ≤ a_{x,y} ≤ 10^{16}, where a_{x,y} is the amount of uninteresting problems Omkar should place in the cell (x, y).

After that, you will first receive a single integer q, the amount of journeys that the duck will take. q queries will follow; each query will consist of a single line containing an integer k, the amount of uninteresting problems that the duck ate on that journey. After each query, given that you have determined that the duck visited the cells (x_1, y_1), (x_2, y_2), ..., (x_{2n - 1}, y_{2n - 1}) in that order (it should always be true that (x_1, y_1) = (1, 1) and (x_{2n - 1}, y_{2n - 1}) = (n, n)), you should output 2n - 1 lines so that the j-th line contains the two integers x_j, y_j.

Bear in mind that if the sum on your path is k, but your path is different from the actual hidden path, then your solution is still wrong!

After printing each line do not forget to output end of line and flush the output. Otherwise, you will get Idleness limit exceeded. To do this, use:

  * fflush(stdout) or cout.flush() in C++;
  * System.out.flush() in Java;
  * flush(output) in Pascal;
  * stdout.flush() in Python;
  * see documentation for other languages.



Hack Format

To hack, first output a line containing n and another line containing q. It must be true that 2 ≤ n ≤ 25 and 1 ≤ q ≤ 1000. Then, output the q journeys taken by the duck in the same format as described above: for each journey, given that the duck visited the cells (x_1, y_1), (x_2, y_2), ..., (x_{2n - 1}, y_{2n - 1}) in that order, you should output 2n - 1 lines so that the j-th line contains the two integers x_j, y_j. It must be true that (x_1, y_1) = (1, 1) and (x_{2n - 1}, y_{2n - 1}) = (n, n). Additionally, for each j such that 2 ≤ j ≤ 2n - 1, it must be true that 1 ≤ x_j, y_j ≤ n and either (x_j, y_j) = (x_{j - 1} + 1, y_{j - 1}) or (x_j, y_j) = (x_{j - 1}, y_{j - 1} + 1).

Example

Input


4




3
23







26







27









Output


1 2 3 6
4 6 2 10
9 0 7 3
2 8 8 2


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

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

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

Note

The duck's three journeys are illustrated below.

1 + 2 + 3 + 2 + 10 + 3 + 2 = 23 

<image>

1 + 4 + 9 + 0 + 7 + 3 + 2 = 26 

<image>

1 + 2 + 3 + 6 + 10 + 3 + 2 = 27 

<image>

Solution (in JAVA):

Solution:
import java.io.*;
import java.util.*;

public class E {
static class Pair<E, V> implements Comparable<Pair<E, V>>{
       E a;
       V b;
       public Pair(E x, V y) {a = x;b=y;}
       public int compareTo(Pair<E, V> p){
           return Integer.compare((Integer)a, (Integer)p.a);
       }
//        @Override
//        public int hashCode() {
//            final int prime = 31;
//            int result = 1;
//            result = prime * result + (Integer)a;
//            result = prime * result + (Integer)b;
//           
//            return result;
//        }
//        @Override
//        public boolean equals(Object obj) {
//            Pair<E, V> cur = (Pair<E, V>)obj;
//            if((Integerx)a == (Integer)cur.a && (Integer)b == (Integer)cur.b)return true;
//            if((Integer)b == (Integer)cur.a && (Integer)a == (Integer)cur.b)return true;
//            return false;
//        }
 } 
static class Spell implements Comparable<Spell>{
	int tp, d;
	public Spell(int tp, int d) {
		this.tp = tp;
		this.d = d;
	}
	@Override
	public int compareTo(Spell o) {
		return Integer.compare(o.tp, tp);
	}
}
public static void main(String[] args){
   new Thread(null, null, "Anshum Gupta", 99999999) {
        public void run() {
            try {
                solve();
            } catch(Exception e) {
                e.printStackTrace();
                System.exit(1);
            }
        }
    }.start();
}
public static long gcd(long a,long b)
{
  if(a<b)
    return gcd(b,a);
  if(b==0)
    return a;
  return gcd(b,a%b);
  
}
static long lcm(int a,int b) {
  return  a*b / gcd(a,b);
}
static int[] z(char[]arr) {
    int l = 0, r = 0;
    int[]z = new int[n];
    for(int i=1; i<n; i++) {
        if(i > r) {
            l = r = i;
            while(r < n && arr[r-l] == arr[r])r++;
            z[i] = r-- - l;
        }else {
            int k = i - l;
            if(z[k] < r - i + l)z[i] = z[k];
            else {
                l = i;
                while(r < n && arr[r-l] == arr[r])r++;
                z[i] = r-- - l;
            }
        }
    }
    return z;
}   
static long pow(long x,long y){
    if(y == 0)return 1;
    if(y==1)return x;
    long a = pow(x,y/2);
    a = (a*a)%mod;
    if(y%2==0){
        return a;
    }
    return (a*x)%mod;
}
static long my_inv(long a) {
    return pow(a,mod-2);
}
static long bin(int a,int b) {
    if(a < b || a<0 || b<0)return 0;
    return ((fact[a]*inv_fact[a-b])%mod * inv_fact[b])%mod;
}
static void make_facts() {
  fact=new long[mxN];
  inv_fact = new long[mxN];
  fact[0]=inv_fact[0]=1L;
  for(int i=1;i<mxN;i++) {
       fact[i] = (i*fact[i-1])%mod;
//       inv_fact[i] = my_inv(fact[i]);
  }
}
static final long mxx = (long)(1e18+5);
static final int mxN = (int)(4e5+5);
static final int mxV = (int)(1e5+5), log = 18;
static long mod = (long)(1e9+7); //998244353;//̇
static long[]fact, inv_fact;
static final int INF = (int)1e9;
static boolean[][]vis;
static ArrayList<ArrayList<Integer>> adj;
static int n, m, k, q, x, y, d;
static char[]str;
static char[][]arr;
static long ans = 0;
public static void solve() throws Exception {
	   // solve the problem here
			s = new MyScanner();
	   		out = new PrintWriter(new BufferedOutputStream(System.out), true);
//	   		out = new PrintWriter("output.txt");
	        int tc = 1;//s.nextInt();
	        while(tc-->0){
	        	n = s.nextInt();
	        	long[][]a = new long[n+1][n+1];
	        	for(int i=1; i<=n; i++) {
	        		for(int j=1; j<=n; j++) {
	        			if(i % 2 == 0) {
	        				a[i][j] = (1L << (i+j));
	        			}
	        			out.print(a[i][j] + " ");
	        		}out.println();
	        	}
	        	out.flush();	
	        	q = s.nextInt();
	        	while(q-- > 0) {
		        	int x = 1, y = 1;
	        		long k = s.nextLong();
	        		while(x < n || y < n) {
	        			out.println(x + " " + y);
	        			if(x == n) {
	        				y++;
	        			}else if(y == n) {
	        				x++;
	        			}else {
	        				if((k & (1L << (x+y+1))) > 0) {
	        					{
	        						if(x % 2 == 0)y++;
	        						else x++;
	        					}
	        				}else {
	        					if(x % 2 != 0)y++;
        						else x++;
	        				}
	        			}
	        		}
	        		assert(x == n && y == n);
	        		out.println(x + " " + y);
	        		out.flush();
	        	}
	        } 
	           
	        out.flush();
	        out.close();
	}

public static PrintWriter out;
public static MyScanner s;
static class MyScanner {

    BufferedReader br;
    StringTokenizer st;

    public MyScanner() {
        br = new BufferedReader(new InputStreamReader(System.in));
    }
    public MyScanner(String fileName) {
    	try {
			br = new BufferedReader(new FileReader(fileName));
		} catch (FileNotFoundException e) {
			e.printStackTrace();
		}
    }
    String next() {
        while (st == null || !st.hasMoreElements()) {
            try {
                st = new StringTokenizer(br.readLine());
            } catch (IOException e) {
                e.printStackTrace();
            }
        }
        return st.nextToken();
    }

    int nextInt() { return Integer.parseInt(next()); }
    long nextLong() { return Long.parseLong(next()); }
    double nextDouble() { return Double.parseDouble(next()); }
    int[] nextIntArray(int n){
    	int[]a = new int[n];
    	for(int i=0; i<n; i++) {
    		a[i] = this.nextInt();
    	}
    	return a;
    }
    long[] nextlongArray(int n) {
    	long[]a = new long[n];
    	for(int i=0; i<n; i++) {
    		a[i] = this.nextLong();
    	}
    	return a;
    }
    Integer[] nextIntegerArray(int n){
    	Integer[]a = new Integer[n];
    	for(int i=0; i<n; i++) {
    		a[i] = this.nextInt();
    	}
    	return a;
    }
    Long[] nextLongArray(int n) {
    	Long[]a = new Long[n];
    	for(int i=0; i<n; i++) {
    		a[i] = this.nextLong();
    	}
    	return a;
    }
    char[][] next2DCharArray(int n, int m){
    	char[][]arr = new char[n][m];
    	for(int i=0; i<n; i++) {
    		arr[i] = this.next().toCharArray();
    	}
    	return arr;
    }
    ArrayList<ArrayList<Integer>> readUndirectedUnweightedGraph(int n, int m) {
    	ArrayList<ArrayList<Integer>>adj = new ArrayList<ArrayList<Integer>>();
    	for(int i=0; i<=n; i++)adj.add(new ArrayList<Integer>());
    	for(int i=0; i<m; i++) {
    		int u = s.nextInt();
    		int v = s.nextInt();
    		adj.get(u).add(v);
    		adj.get(v).add(u);
    	}
    	return adj;
    }
    ArrayList<ArrayList<Integer>> readDirectedUnweightedGraph(int n, int m) {
    	ArrayList<ArrayList<Integer>>adj = new ArrayList<ArrayList<Integer>>();
    	for(int i=0; i<=n; i++)adj.add(new ArrayList<Integer>());
    	for(int i=0; i<m; i++) {
    		int u = s.nextInt();
    		int v = s.nextInt();
    		adj.get(u).add(v);
    	}
    	return adj;
    }
    String nextLine(){
        String str = "";
        try {
            str = br.readLine();
        } catch (IOException e) {
            e.printStackTrace();
        }
        return str;
    }
}

 
}