Problem description

Dane są dwie liczbowe tablice N-elementowe. Elementy jednej tablicy są podane. W drugiej zaś tablicy i-ty element jest równy Ai³ + Bi² + Ci + D (stałe A, B, C, D także są znane i podane). Rozważmy tablicę 2N-elementową, w której najpierw umieszczamy elementy pierwszej tablicy, potem zaś elementy drugiej i sortujemy ją. Należy wyznaczyć K-ty element nowej, tak posortowanej tablicy.

Takich pytań jest wiele dla różnych tablic, więc potrzebny jest szybki program. Tablica pierwsza jest wspólna dla wszystkich zapytań, zaś stałe A, B, C, D oraz wartość K mogą być różne dla każdego zapytania.

Napisz program, który wczyta opis elementów pierwszej tablicy i zapytania (stałe, którymi opisana jest druga tablica oraz wartość K), wyznaczy odpowiedzi na wszystkie zapytania i wypisze wyniki na standardowe wyjście.

Wejście

W pierwszym wierszu wejścia znajdują się dwie liczby naturalne N i Q, określające długość jednej tablicy oraz liczbę zapytań. W drugim wierszu wejścia znajduje się ciąg N nieujemnych liczb całkowitych T_i, pooddzielanych pojedynczymi odstępami. Są to elementy pierwszej tablicy.

W kolejnych Q wierszach znajdują się opisy kolejnych zapytań. Opis każdego zapytania składa się z pięciu nieujemnych liczb całkowitych A_i, B_i, C_i, D_i, K_i, pooddzielanych pojedynczymi odstępami. Pierwsze cztery liczby opisują stałe A, B, C, D generujące drugą tablicę, zaś K_i określa który z kolei element chcemy uzyskać po posortowaniu.

Zakładamy wyjątkowo, że tablice są indeksowane od 1.

Wyjście

Twój program powinien wypisać na wyjście dokładnie Q wierszy. W i-tym wierszu powinna się znaleźć odpowiedź dla i-tego zestawu danych. Odpowiedź dla każdego zestawu danych powinna się składać z jednej liczby całkowitej – liczby, która byłaby na K_i-tej pozycji w posortowanej niemalejąco tablicy powstałej ze sklejenia tablicy pierwszej i drugiej tablicy z i-tego zapytania.

Ograniczenia

1 ≤ N ≤ 500 000, 1 ≤ Q ≤ 500 000, 1 ≤ K_i ≤ 2 ⋅ N, 0 ≤ T_i ≤ 10¹⁸, 0 ≤ A_i, B_i, C_i, D_i ≤ 10⁹.

Dane testowe będą tak dobrane, żeby AN³ + BN² + CN + D ≤ 10¹⁸.

W testach wartych łącznie 35% maksymalnej punktacji zachodzi dodatkowy warunek: N ≤ 2 000, Q ≤ 5 000.

W testach wartych łącznie 75% maksymalnej punktacji zachodzi dodatkowy warunek: N ≤ 100 000, Q ≤ 100 000.

Przykład

5 2
2 15 29 46 6
1 0 2 1 3
0 1 1 1 7

6
21