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.