Subtask 1

Brute force suffices.

Time Complexity: ~\mathcal{O}(NQ)~

Subtask 2

Notice for each type of query:

1 w: denotes ~\max(\max_{i=1}^n y_i, x_w)~.

• If the array ~y~ is sorted, the values in the column are ordered as: ~\max(y_1, x_w) \le \max(y_2, x_w) \le \dots \le \max(y_n, x_w)~. The maximal value is: ~\max(y_n, x_w)~.

2 w: denotes ~\max(\min_{i=1}^n y_i, x_w)~.

• If the array ~y~ is sorted, the values in the column are ordered as: ~\max(y_1, x_w) \le \max(y_2, x_w) \le \dots \le \max(y_n, x_w)~. The minimal value is: ~\max(y_1, x_w)~.

3 w: denotes ~\max(\max_{i=1}^n x_i, y_w)~.

• If the array ~x~ is sorted, the values in the row are ordered as: ~\max(x_1, y_w) \le \max(x_2, y_w) \le \dots \le \max(x_n, y_w)~. The maximal value is: ~\max(x_n, y_w)~.

4 w: denotes ~\max(\min_{i=1}^n x_i, y_w)~.

• If the array ~x~ is sorted, the values in the row are ordered as: ~\max(x_1, y_w) \le \max(x_2, y_w) \le \dots \le \max(x_n, y_w)~. The minimal value is: ~\max(x_1, y_w)~.

The ~\max~ and ~\min~ of arrays ~x~ and ~y~ can be found in ~\mathcal{O}(N)~ time and stored before answering any queries.

Time Complexity: ~\mathcal{O}(N+Q)~