You are given an integer array $$$a$$$ containing $$$n$$$ elements.

You can do the following operation on array $$$a$$$ :

1. Choose two integers $$$a_{i}$$$, $$$a_{j}$$$ $$$(i ≠ j)$$$.
2. If $$$(a_{i} + a_{j})$$$ is even, then remove $$$a_{i}$$$, $$$a_{j}$$$ from $$$a$$$ and add $$$(a_{i} + a_{j})$$$ at the end of $$$a$$$.

What are the minimum number of elements in $$$a$$$ after performing the above operation for at most $$$k$$$ times.

You are given an integer array $$$a$$$ containing $$$n$$$ elements.

A pair $$$(l, r) (1 \le l \le r \le n)$$$ is called Normal pair, if $$$^\dagger$$$ $$$MEX(a_{l},a_{l+1},....,a_{r-1},a_{r})$$$ has maximum value among all other pairs.

Out of all possible Normal pairs, find a pair $$$(l, r)$$$ which has a minimum value of $$$(r-l+1)$$$.

$$$^\dagger$$$ $$$MEX(b)$$$ is defined as the smallest non-negative integer which is not present in $$$b$$$. For example $$$MEX(1, 0, 3) = 2$$$, $$$MEX(2, 5, 3) = 0$$$.

You are given an integer array $$$a(a_{1},a_{2},....,a_{n})$$$containing $$$n$$$ elements, it is guaranteed that $$$n$$$ is even.

Let's define some definitions:

• $$$S_{1}(a)$$$ is defined as set of elements in $$$a$$$ at odd index positions. i.e., $$$S_{1}(a) = (a_{1},a_{3},....,a_{n-1})$$$.
• $$$S_{2}(a)$$$ is defined as set of elements in $$$a$$$ at even index positions. i.e., $$$S_{2}(a) = (a_{2},a_{4},....,a_{n})$$$.
• $$$R(S)$$$ is defined as the Range$$$^\dagger$$$ of the set $$$S$$$.
• $$$f(a) = R(S_{1}(a))*R(S_{2}(a))$$$

You are allowed to do the following operation on $$$a$$$:

• Choose $$$i,j(1 \le i,j \le n)$$$ and swap $$$a_{i}$$$ and $$$a_{j}$$$.

Let the array $$$b$$$ be the resultant array $$$a$$$ after performing above operation any times(possibly zero).

Output any $$$b$$$ which has minimum $$$f(b)$$$.

$$$^\dagger$$$ Range of the set $$$S$$$ is defined as the difference between the maximum element and minimum element in $$$S$$$.

You are given a binary string$$$^\dagger$$$ $$$S$$$ of length $$$n$$$.

For a given non-negative integer $$$m$$$ you can choose any binary string $$$P$$$ of length $$$n$$$ which contains $$$m$$$ $$$1's$$$ and $$$(n-m)$$$ $$$0's$$$.

Let the binary string $$$T = S \oplus P$$$, where $$$\oplus$$$ denotes Bitwise XOR

What are the maximum number of contiguous substrings of length $$$2$$$ in $$$T$$$ which are equal to $$$'11'$$$.

Solve the above problem for every $$$m(0 \le m \le n)$$$ .

$$$^\dagger$$$ A binary string is a string which only contains $$$0's$$$ and $$$1's$$$.

You are given two integer arrays $$$a(a_{0},a_{1},....,a_{n-1})$$$ containing $$$n$$$ elements, $$$b(b_{0},b_{1},....,b_{n-1})$$$ containing $$$n$$$ elements and an integer $$$k$$$.

You are allowed to do the following popular segment tree Operation on array $$$a$$$.

1. Choose any value $$$l(0 \le l \le n-1)$$$.
2. Let $$$sum$$$ = $$$(a_{(l-k)\%n}+a_{(l-k+1)\%n}+....+a_{l-1}+a_{l}+a_{l+1}+....+a_{(l+k-1)\%n}+a_{(l+k)\%n})$$$.
3. Update $$$a_{l}$$$ = $$$sum$$$.

Find the minimum number of Operations required to change $$$a$$$ to $$$b$$$ or report if it is impossible to do.

Note that, $$$x\%y$$$ is the remainder when $$$y$$$ divides $$$x$$$. i.e., $$$(10\%4) = 2$$$, $$$(-5\%4) = 3$$$.

This is the easy version of the problem. The changes in this version are highlighted in bold characters.

Yugandhar have an undirected graph containing $$$n$$$ nodes numbered $$$1,2,....,n$$$. Initially there are $$$0$$$ edges i.e., there are total $$$n$$$ connected components in the graph. He has a freedom to add exactly $$$k$$$ undirected edges in this graph, each edge can be added between $$$u$$$ and $$$v$$$ if and only if $$$v$$$ = $$$u+1$$$. Note that he can add multiple edges between two nodes.

After giving this graph to wuhudsm, he will observe the following $$$m$$$ requirements and reward him coins :

• If wuhudsm can able to reach $$$y_{i}$$$ from $$$x_{i}$$$ then he will reward him $$$c_{i}$$$ coins.

So Please tell him the optimal way to select these $$$k$$$ edges to get maximum number of coins.

Aditionally, help him for $$$q$$$ queries.

This is the hard version of the problem. The changes in this version are highlighted in bold characters.

Yugandhar have an undirected graph containing $$$n$$$ nodes numbered $$$1,2,....,n$$$. Initially there are $$$0$$$ edges i.e., there are total $$$n$$$ connected components in the graph. He has a freedom to add exactly $$$k$$$ undirected edges in this graph, each edge can be added between $$$u$$$ and $$$v$$$ if and only if $$$v$$$ = $$$u+1$$$. Note that he can add multiple edges between two nodes.

After giving this graph to wuhudsm, he will observe the following $$$m$$$ requirements and reward him coins :

• If wuhudsm can able to reach $$$y_{i}$$$ from $$$x_{i}$$$ then he will reward him $$$c_{i}$$$ coins.

So Please tell him the optimal way to select these $$$k$$$ edges to get maximum number of coins.

Aditionally, help him for $$$q$$$ queries.