26840번 - Podzielność 다국어

Ostatnio na lekcji informatyki Bajtuś uczył się o pozycyjnych systemach liczbowych. Dowiedział się m.in., że ludzie najczęściej korzystają z naturalnego dla nich dziesiątkowego systemu liczbowego, a komputery zapisują liczby w systemie dwójkowym. Jednak dowolna liczba naturalna B większa od 1 może stać się podstawą systemu liczbowego. W takim systemie dysponujemy cyframi 0, 1, 2, . . . , B−2, B−1, a k-cyfrowy zapis złożony z kolejnych cyfr c_k−1c_k−2 . . . c₂c₁c₀ oznacza liczbę

c_k−1 · B^k−1 + c_k−2 · B^k−2 + . . . + c₂ · B² + c₁ · B + c₀.

Przykładowo, w trójkowym systemie pozycyjnym zapis 201 oznacza liczbę 2 · 3² + 0 · 3 + 1, czyli 19 w systemie dziesiętnym (w skrócie możemy to zapisać jako 201₃ = 19₁₀).

Bajtuś wybrał pewną liczbę B jako podstawę systemu liczbowego i napisał na karteczkach wszystkie możliwe cyfry w tym systemie, niektóre być może wielokrotnie: dla i = 0, 1, . . . , B −1 ma on ai karteczek z cyfrą i. Chciałby ułożyć z nich jak największą liczbę podzielną przez B − 1. Napisz program, który mu w tym pomoże. Szukana liczba może być bardzo duża, jednak Bajtusiowi wystarczy, że podasz tylko niektóre jej cyfry. Przyjmujemy, że zapis liczby dodatniej nie może zaczynać się od zer wiodących, a jedyny zapis zera to 0.

Uwaga: Zakładamy, że w przypadku systemów pozycyjnych o podstawie większej niż 10, cyfry w zapisie liczby są rozdzielone np. odstępami, dzięki czemu nie ma problemu z podziałem liczby na poszczególne cyfry.

W pierwszym wierszu standardowego wejścia znajdują się dwie liczby całkowite B oraz q (B ≥ 2, q ≥ 1) oddzielone pojedynczym odstępem, oznaczające podstawę systemu liczbowego i liczbę pytań o cyfry szukanej przez Bajtusia liczby.

Drugi wiersz zawiera ciąg B liczb całkowitych a₀, a₁, . . . , a_B−1 (a_i ≥ 1) pooddzielanych pojedynczymi odstępami, oznaczających liczby karteczek z kolejnymi cyframi, które są w posiadaniu Bajtusia.

Następne q wierszy zawiera pytania: i-ty z tych wierszy zawiera jedną liczbę całkowitą k_i (0 ≤ k_i ≤ 10¹⁸).

Na standardowe wyjście należy wypisać dokładnie q wierszy; i-ty z nich musi zawierać k_i-tą cyfrę największej liczby w systemie o podstawie B podzielnej przez B − 1, którą może ułożyć Bajtuś, wykorzystując posiadane karteczki. Cyfry numerujemy według wzoru podanego powyżej: od prawej strony (czyli od najmniej znaczących cyfr) i począwszy od 0. Jeśli szukana liczba ma mniej niż k_i cyfr, w i-tym wierszu należy wypisać −1.

• B, a_i ≤ 1 000 000, q ≤ 100 000

Wyjaśnienie do przykładu: Mając po jednej cyfrze 0, 1 i 2 w trójkowym systemie liczbowym, Bajtuś może ułożyć liczby 0₃ = 0₁₀, 1₃ = 1₁₀, 2₃ = 2₁₀, 10₃ = 3₁₀, 12₃ = 5₁₀, 20₃ = 6₁₀, 21₃ = 7₁₀, 102₃ = 11₁₀, 120₃ = 15₁₀, 201₃ = 19₁₀ oraz 210₃ = 21₁₀. Przez 2 podzielne są jedynie 0₃, 2₃ oraz 20₃, zatem szukana liczba to 20₃.