8708번 - Sprężyny 다국어

Bajtoś dostał nową kolekcję sprężyn. Każda z nich została wyprodukowana w pewnych wymiarach, a każde jej rozciągnięcie, bądź ściśnięcie, wymaga dość sporego wysiłku.

Aby wydłużyć lub skrócić o 1 centymetr nieruszaną jeszcze sprężynę, potrzeba 1 jednostki wysiłku. Każde kolejne rozciągnięcie, bądź ściśnięcie, tej samej sprężyny wymaga dodatkowo zwiększenia wysiłku o 1. Dokładniej, jeśli Bajtoś chce wydłużyć sprężynę o d centymetrów, to będzie się wysilał o kolejno 1, 2, ..., d jednostek wysiłku.

Bajtoś zastanawia się, ile minimalnie wysiłku musi włożyć, aby k najkrótszych sprężyn było tej samej długości. Zakładamy, że wszystkie sprężyny Bajtosia nie były dotąd rozciągane ani ściskane.

Pierwszy wiersz standardowego wejścia zawiera dwie liczby całkowite n, m (1 ≤ n, m ≤ 10⁶), oznaczające odpowiednio liczbę sprężyn oraz liczbę zapytań Bajtosia. Kolejny wiersz zawiera n liczb całkowitych s₁, s₂, ..., s_n (1 ≤ s_i ≤ s_i+1 ≤ 10⁹), gdzie s_i oznacza długość i-tej sprężyny. Następny wiersz zawiera m liczb całkowitych k₁, k₂, ..., k_m (1 ≤ k_j ≤ n), gdzie k_j oznacza j-te zapytanie Bajtosia, w którym wybiera k_j najmniejszych sprężyn.

j-ty wiersz wyjścia powinien być odpowiedzią na j-te zapytanie (to jest ile minimalnie wysiłku kosztowałoby Bajtosia ustawienie k_j najkrótszych sprężyn na tą samą długość) modulo 10⁹ + 7.