We can do one of the following 2 things -
- Either write both strings without using 2nd action
- Or we first write longest common prefix string, then use 2nd action and then write the remaining strings.

Use pen and paper and write down table C.

Table C looks like this -

1             
1 1              
1 2 1              
1 2 4 1            
1 2 4 8 1             
1 2 4 8 16 1             

If $$$k=n$$$, $$$C[n][k] = 1$$$, else $$$C[n][k]=2^k$$$

Sort the array and then use two pointers

Alternatively,
Sort the array and then for each fixed L, binary search largest R such that you can take all elements in subarray [L...R]

dp[i][x][y] denotes maximum checks among first i queries that we can pass if our current intelligence level is x and current strength level is y.

Its never optimal to leave any acquiring point. So x+y will always be no of rj=0 for j<=i.

This allows us to remove one dp dimension.

dp[i][y] denotes maximum checks among first i queries that we can pass if we have used y attribute points for strength, and all remaining points for intelligence.

Whenever we have ri < 0, we essentially do +1 to a suffix in above dp array.
Whenever we have ri > 0, we essentially do +1 to a prefix in above dp array.

For ri=0,
If we increase strength, we can do dp[i][y]=max(dp[i][y],dp[i-1][y-1])
If we increase intelligence, we can do dp[i][y]=max(dp[i][y],dp[i-1][y])

If we use lazy segment tree for range addition.
We can solve this problem in $$$O(m^2*logm + n*logm)$$$.
$$$O(m*logm)$$$ per attribute point query, and $$$O(logm)$$$ per check query.

We can even do better, without using any segment tree.
Lets maintain difference array for dp[i][*] table.
So range additions are just +1 and -1 at 2 places.

Allowing us to do this O(m^2+n).

Refer implementation for more details.

Lets pick a suite and distribute m cards in descending order.

Lets say we have distributed all cards between [i...m], we have given p1 cards to first player and p2 cards to second player.
Let Y denotes minimum no of suite 1 cards we need for this assignment.
Let dP = p1-p2

Now, we can use dp here,
dp[i][dP][Y] denotes above state.

Y is essentially minimum possible value of dP when we are assigning all the cards.

The transitions are as follows -
If we assign i-1 card to first player dp[i-1][dP+1][Y]+=dp[i][dP][Y]
If we assign i-1 card to second player dp[i-1][dP-1][min(Y,dp-1)]+=dp[i][dP][Y]

Another important observation is we can only give away equal no of cards to both the player if dp=Y for every suites except 1, ie we only need dp[1][X][X]

Another important observation is -
No of suite 1 cards assigned to first player >= No of suite 1 cards assigned to second player.

For all other suites 2<=j<=n,
No of suite j cards assigned to first player <= No of suite j cards assigned to second player.

Now, we can first fix the no of extra suite 1 cards (say K) we want to give to first player.

Let the no of extra cards given to second play for other suites be x2,x3,...,xn.

Then we need x2+x3+...+xn = K.
This part can be done using knapsack.

Its possible to solve this problem for following constraints -
- N <= 10^18
- M <= 500

Let first decide if we want to do an operation on xi or yi.

We can ensure that each ai is either 0 or 1.
Do -1 if ai is 1, and +1 if ai is 0.

Now, lets create a graph with n nodes and q edges.
ith edge connects xi and yi.

Selecting xi or yi for each query is equivalent to giving a direction to each edge in this graph.

If edge is directed from xi -> yi, we select xi.
If edge is directed from yi -> xi, we select yi.

au will be equal to parity of no of incoming edges on u.

Formally, we have a graph with n nodes, and q edges.
We want to assign direction to each edge such that no of nodes with odd parity of incoming is minimum possible.

This is quite a well known problem (CodeChef EDGEDIR), and have appeared quite many times.

For each connected components, if no of edges is odd, then its possible to direct edges in such a way that only one node has odd parity of incoming edges.
For each connected components, if no of edges is even, then its possible to direct edges in such a way that all nodes have even parity of incoming edges.