Sinulle on annettu kaksi taulukkoa $A$ ja $B$, joiden koot ovat $n$ ja $m$. Olkoon $C$ taulukko, jonka koko on $n m$, ja jonka arvo kohdassa $i + n j$ ($0 \leq i < n$, $0 \leq j < m$) on $A[ i ] + B[ j ]$. Tehtäväsi on vastata välin minimi -kyselyihin tässä taulukossa. Kyselyt ovat satunnaisia ja enkoodattuja.

Syöte

Ensimmäisellä rivillä on kaksi kokonaislukua $n$, $m$: taulukkojen $A$ ja $B$ koot.

Toisella rivillä on $n$ kokonaislukua $A[ 0 ], \dots, A[ n - 1]$: taulukon $A$ arvot.

Kolmannella rivillä on $n$ kokonaislukua $B[ 0 ], \dots, B[ m - 1 ]$: taulukon $B$ arvot.

Neljännellä rivillä on kaksi lukua $q, x_0$: kyselyiden määrä ja satunnaisgeneraattorin seed.

Seuraava koodi generoi kyselyt:

uint64_t nextRandom(uint64_t& x) {
        ull z = (x += 0x9e3779b97f4a7c15);
        z = (z ^ (z >> 30)) * 0xbf58476d1ce4e5b9;
        z = (z ^ (z >> 27)) * 0x94d049bb133111eb;
        return z ^ (z >> 31);
}
int solve(int nm, int q, uint64_t x) {
        int ans;
        for (int qi = 0; qi < q; ++qi) {
                int l = nextRandom(x) % nm;
                int r = nextRandom(x) % nm;
                if (l > r) swap(l, r);

                ans = rangeMin(l, r); // Implement this
                x ^= ans;
        }
        return ans;
}

Jokainen kysely on kutsu funktioon rangeMin.

Tuloste

Palauta funktion solve palauttama arvo, kun sitä kutsutaan parametreilla $n \cdot m, q$ ja $x_0$, ja funktio RangeMin(l, r) korvataan välin $[l, r]$ minimin laskemisella taulukossa C.

Rajat

• $1 \leq n, m \leq 10^5$, $1 \leq n m \leq 10^7$.
• $1 \leq q \leq 10^7$
• $0 \leq A[ i ], B[ j ] \leq 10^9$
• $0 \leq x_0 \leq 2^{64} - 1$

Esimerkki

Syöte:

3 3
1 2 3
6 3 0
5 0

Tuloste:

1

Selitys: Tässä taulukko $C$ on 7 8 9 4 5 6 1 2 3. Kyselyt vastaavat välejä $[0, 7]$, $[2, 3]$, $[2, 7]$, $[7, 8]$ ja $[6, 8]$, ja vastaukset niihin ovat $1, 4, 1, 2$ ja $1$.