Try to solve the following problem, only by combining meaning but not the generating function.

There are q times inquiries, Given k, P, a, each time, print the value of this sum, $$$q,k,P,a \leq 1e5$$$.

I'll give an answer in 24 hours. If solved, please write the method in the comments and try the harder problems below, which replace 2 by t, t will be given before all queries.

Given are Permutations of $$$(1,2,...N):p(p_1, p_2,...,p_N),q(q_1, q_2, ..., q_N)$$$

When you choose a number in the first permutation, the same position in the second permutation and the same value in the second permutation are both banned.

For example： $$$p:(1,3,2,4), q:(1,2,3,4)$$$

When you choose $$$p[2]=3$$$, you can't choose $$$q[2]$$$ which has the same position and also can't choose $$$q[3]=3$$$ which has the same value.

Find the ways of choose $$$i$$$ elements in the first permutation and left $$$j$$$ elements in the second permutation not banned, for every $$$i, j \leq N$$$

$$$N \leq 3000$$$.

The original problem link

I misread the problem, and lead to a SUPER HARD one.

Different from the original problem I want to fix S and T and ask whether there exists an answer.

Can anyone help me?