Dynamic Bipartite Matching with Subarray Queries

Little S has recently learned the Hungarian algorithm for bipartite matching. In this problem, you are given a bipartite graph \(G = (X, Y, E)\) defined as follows:

• Set \(X\) contains \(N\) numbers \(A_i\) (\(1 \le i \le N\)).
• Set \(Y\) is formed dynamically by choosing a contiguous subarray from an array \(B\) of length \(M\). In a query, you are given indices \(L\) and \(R\) (1-indexed), and the numbers \(C_j\) in \(Y\) are precisely \(B_L, B_{L+1}, \dots, B_R\). Let \(K = R-L+1\) be the size of \(Y\).
• An edge exists between \(A_i\) and \(C_j\) (from \(Y\)) if and only if \(A_i + C_j \le Z\) (i.e. \(A_i + C_j \le Z\)).

Your task is to compute the maximum matching in the bipartite graph \(G=(X,Y,E)\) for each query. Since Little S is practicing, she performs \(Q\) queries, each one defined by a pair \(L, R\) that selects the current \(Y\) set. For each query, output the maximum matching size.

Note: All formulas are written in \(\LaTeX\) format.

inputFormat

The first line contains four integers \(N\), \(M\), \(Q\), and \(Z\) — the number of elements in array \(A\), the length of array \(B\), the number of queries, and the threshold, respectively. The second line contains \(N\) integers: \(A_1, A_2, \dots, A_N\). The third line contains \(M\) integers: \(B_1, B_2, \dots, B_M\). Each of the next \(Q\) lines contains two integers \(L\) and \(R\) (1-indexed), representing a query where the subarray \(B_L, B_{L+1}, \dots, B_R\) will act as the set \(Y\).

outputFormat

For each query, output a single line with one integer — the size of the maximum matching in the corresponding bipartite graph.

sample

3 5 2 10
1 2 3
3 4 5 6 7
1 3
2 5

3
3