Background

A fantasy castle sits among a small forest. This is the territory of Country E, and Little E is the king of Country E.

Trees are Country E's magic weapon to resist attacks. The taller the trees are, the better they can block the enemies' view.

However, as natural conditions get worse, Little E does not know what to do. What should he do?

Problem Description

Given an $n$ by $n$ matrix $a$.

There are $q$ queries. In each query, a value $v$ is given. You may arbitrarily reorder each row of the matrix (or choose not to reorder it) to maximize the number of columns whose maximum value is not less than $v$ (that is, in that column, there is at least one number that is not less than $v$). Output this number of columns.

The queries are independent. In other words, you may reorder the matrix again before each query.

Input Format

The first line contains two positive integers $n, q$.

Lines $2$ to $n + 1$ each contain $n$ positive integers, representing the matrix $a$.

Then follow $q$ lines, each containing one positive integer $v$, representing a query.

Output Format

For each query, output one line containing one integer, representing the answer.

3 3
9 9 8
2 4 4
3 5 3
5
9
10

3
2
0

Hint

Sample Explanation

The original matrix is $\begin{bmatrix}9&9&8\\2&4&4\\3&5&3\end{bmatrix}$.

For the first query, the maximum value of each column is $9, 9, 8$, all of which are not less than $v = 5$, so every column satisfies the condition and the answer is $3$. Obviously, no matter how you reorder, it is impossible to exceed $3$ columns (because there are only $3$ columns in total), so the answer is $3$.

Constraints

This problem uses bundled testdata.

For all testdata, $1 \leq n \leq 10^3$, $1 \leq q \leq 5\times 10^5$, and $1 \leq a_{i,j}, v \leq 10^9$.

Translated by ChatGPT 5