Џамлија (или скокалче, газоза, кликер, зуска...) е мало камено, стаклено или железно топче со кое си играат децата. Ги има во повеќе различни бои и шари.

Во продавница за играчки има неограничени количества од џамлии од N типови, секој од нив со по соодветно a₁, a₂, ..., a_N различни бои. Пристигнале M порачки до продавницата. Секоја нарачка ги има следните барања:
1) Треба да се направат K различни пакетчиња. Секое пакетче мора да има ист број на џамлии. (Две пакетчиња се различни ако се разликуваат барем во еден тип на џамлии кои се искористени);
2) Може да се користат само џамлии кои имаат барем L, но не повеќе од R бои;
3) Во секое пакетче може да има најмногу една џамлија од секој тип.

Продавачот сака да искористи што е можно помалку џамлии за секоја порачка. За секоја порачка утврдете го тој минимален број на џамлии што се потребни за да се задоволи порачката.

Влез

Во првиот ред се дадени два позитивни цели броеви: N (1 ≤ N ≤ 3000) и M (1 ≤ M ≤ 10⁴), бројот на различни типови на џамлии, и бројот на порачки, соодветно.
Во вториот ред се дадени N позитивни цели броеви a₁, a₂, ..., a_N (1 ≤ a_i ≤ 10⁵) кои го претставуваат бројот на бои за секој тип на џамлии.
Во следните M редови се дадени по три позитивни цели броеви L, R (1 ≤ L ≤ R ≤ 10⁵) и K (1 ≤ K ≤ 10⁹⁰¹), кои ја опишуваат секоја од нарачките.

Забелешка.
Подзадача 1: 11 поени, N ≤ 15, K ≤ 250
Подзадача 2: 13 поени, N ≤ 50, K ≤ 10¹⁸, зависна подзадача: 1
Подзадача 3: 15 поени, N ≤ 100, K ≤ 10⁹⁰¹, зависни подзадачи: 1, 2
Подзадача 4: 19 поени, N ≤ 1350, K ≤ 10⁹⁰¹, M ≤ 10³, зависни подзадачи: 1, 2, 3
Подзадача 5: 20 поени, N ≤ 1450, K ≤ 10⁹⁰¹, зависни подзадачи: 1, 2, 3, 4
Подзадача 6: 5 поени, N ≤ 3000, K = 1, , зависна подзадача: /
Подзадача 7: 17 поени, N ≤ 3000, K ≤ 10⁹⁰¹, зависни подзадачи: 1, 2, 3, 4, 5, 6

Во финалните резултати, поените за дадена подзадача ќе се доделат само ако се успешни сите тест случаи за таа подзадача како и тест случаите од сите подзадачи од кои зависи таа подзадача.

Излез

За секоја нарачка, отпечатете го бараниот број, во посебен ред. Ако дадена порачка не може да се испорача отпечатете -1 за неа.

Ограничувања

Временско ограничување: 1 second
Мемориско ограничување: 256 megabytes

Примери

влез
7 3
3 4 1 1 6 1 2
2 5 3
4 7 3
1 2 5

излез
1
-1
2

Објаснување на примерот:
За првата нарачка, може да се користат џамлиите од тип 1, 2 и 7 (соодветно со 3, 4 и 2 бои). Доколку секое пакетче содржи една џамлија, можат да се направат точно 3 различни пакетчиња.
За втората нарачка, може да се користат џамлиите од тип 2 и 5 (соодветно со 4 и 6 бои). Затоа, не е можно да се направат 3 различни пакетчиња.
За третата нарачка, вкупно 4 типа на џамлии може да се користат. Доколку секое пакетче содржи по 2 џамлии, може да се направат најмалку 5 различни пакетчиња.