W razie problemów technicznych ze Szkopułem, prosimy o kontakt mailowy pod adresem [email protected].
Jeśli chciałbyś porozmawiać o zadaniach, rozwiązaniach lub problemach technicznych, zapraszamy na serwery Discord. Są one moderowane przez społeczność, ale członkowie zespołu technicznego też są tam aktywni.
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 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 centymetrów, to będzie się wysilał o kolejno jednostek wysiłku.
Bajtoś zastanawia się, ile minimalnie wysiłku musi włożyć, aby 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 (), oznaczające odpowiednio liczbę sprężyn oraz liczbę zapytań Bajtosia. Kolejny wiersz zawiera liczb całkowitych (), gdzie oznacza długość -tej sprężyny. Następny wiersz zawiera liczb całkowitych (), gdzie oznacza -te zapytanie Bajtosia, w którym wybiera najmniejszych sprężyn.
Możesz założyć, że w testach wartych łącznie punktów zachodzą dodatkowe warunki i , w testach wartych łącznie punktów zachodzi i , a w testach wartych punktów zachodzi .
-ty wiersz wyjścia powinien być odpowiedzią na -te zapytanie (to jest ile minimalnie wysiłku kosztowałoby Bajtosia ustawienie najkrótszych sprężyn na tą samą długość) modulo .
Dla danych wejściowych:
4 4 1 3 4 10 1 2 3 4
poprawną odpowiedzią jest:
0 2 4 28
Autor zadania: Jacek Tomasiewicz.