Under construction

Still being built. Things may change

Rectangles and Queries

Interview

Time limit2sMemory limit512 MB

Summary
Given an N by N matrix with values at most 10, answer many rectangle queries, each asking how many distinct integers appear inside the submatrix.
Level

Medium5 of 10

Topics
Prefix sum, Matrix, Implementation, Brute force
Solved
No attempts yet

Problem

You are given a square matrix AA with NN rows and NN columns. Write a program that answers queries about it.

  • x1 y1 x2 y2: print the number of distinct integers inside the submatrix whose top left cell is (x1,y1)(x_1, y_1) and whose bottom right cell is (x2,y2)(x_2, y_2).

Input

The first line contains NN (1≤N≤3001 \le N \le 300). Each of the next NN lines contains one row of the matrix as NN numbers. Rows are numbered from top to bottom and columns from left to right, both starting at 1. Every entry of the matrix is a natural number not greater than 10.

The next line contains QQ (1≤Q≤100 0001 \le Q \le 100\,000). Each of the next QQ lines contains one query given as x1x_1, y1y_1, x2x_2, y2y_2, where xx is a row number and yy is a column number. (1≤x1≤x2≤N1 \le x_1 \le x_2 \le N, 1≤y1≤y2≤N1 \le y_1 \le y_2 \le N)

Output

For each query, print the answer on its own line.

Examples1

  1. Example 1

    Input
    3
1 2 3
3 2 1
5 6 3
3
1 1 2 3
2 2 2 2
1 1 3 3
    Expected output
    3
1
5