Contest problemset description

Bajtazar ma bardzo napięty kalendarz. Ciężko pracował, aby wszystko zaplanować i upewnić się, że aktywności się nie nakładają. Teraz jest poranek i martwisz się, że mimo całego entuzjazmu Bajtazarowi może zabraknąć energii.

Na początku dnia Bajtazar zaczyna z planem N aktywności oraz pełnym zapasem E jednostek energii. Aktywności muszą być wykonywane w kolejności 1, …, N, a energia nie może spaść poniżej 0 ani przekroczyć E (wszelka nadwyżka ponad E przepada).

Podczas dnia każda aktywność może zużyć nieujemną liczbę całkowitą jednostek energii wybraną przez Bajtazara. Niezależnie od tego, ile jednostek energii Bajtazar włożył w aktywność, po jej zakończeniu odzyskuje R jednostek energii (lub mniej, jeśli energia miałaby przekroczyć limit E).

Praca wykonana przez Bajtazara dla aktywności i jest równa liczbie poświęconych jej jednostek energii pomnożonej przez wartość aktywności v_i. Aby obliczyć pracę wykonaną przez Bajtazara podczas całego dnia, należy zsumować pracę dla każdej aktywności.

Pomóż Bajtazarowi zarządzać energią podczas dnia tak, aby łączna wykonana przez niego praca była jak największa.

Wejście

W pierwszym wierszu wejścia znajduje się liczba testów T. Następnie podanych jest T testów.

Każdy test składa się z dwóch wierszy.

W pierwszym wierszu są trzy liczby całkowite: maksymalna (i początkowa) liczba jednostek energii E, liczba jednostek energii R odzyskiwana po każdej aktywności oraz liczba aktywności w planie dnia N.

W drugim wierszu jest N liczb całkowitych v_i, opisujących wartości kolejnych aktywności.

Wyjście

Dla każdego testu wypisz w osobnym wierszu największą pracę, jaką może wykonać Bajtazar, odpowiednio zarządzając energią w ciągu dnia.

Ograniczenia

1 ≤ T ≤ 100, 1 ≤ N ≤ 10 000, 1 ≤ E, R, v_i ≤ 10⁷

Podzadania

Przykład

3
5 2 2
2 1
5 2 2
1 2
3 3 4
4 1 3 5

12
12
39

Bajtazar projektuje nowy plakat Olimpiady Informatycznej Juniorów. Po głębokim zastanowieniu postanowił, że plakat będzie miał N wierszy i M kolumn, a każda komórka będzie zawierała małą literę alfabetu angielskiego.

Dodatkowo, Bajtazar bardzo lubi palindromy. Będzie usatysfakcjonowany tylko i wyłącznie gdy dokładnie R wierszy będzie palindromami oraz gdy dokładnie C kolumn będzie palindromami. Pomóż mu w tym i zaprojektuj plakat, który będzie mu się podobał lub stwierdź, że nie jest to możliwe.

Wejście

W pierwszym (i jedynym) wierszu wejścia znajdują się cztery liczby całkowite N,M,R i C oznaczające odpowiednio liczbę wierszy, liczbę kolumn, ile wierszy powinno być palindromami i ile kolumn powinno być palindromami w plakacie.

Wyjście

Należy wypisać N wierszy wyjścia, w każdym po M małych liter alfabetu angielskiego oznaczające projekt plakatu, który zadowoli Bajtazara lub -1 jeżeli nie jest to możliwe.

Jeżeli istnieje wiele możliwych rozwiązań, Twój program może wypisać dowolne z nich.

Ograniczenia

2 ≤ N, M ≤ 2 000

0 ≤ R ≤ N

0 ≤ C ≤ M

Podzadania

Przykład

4 5 1 2

oijio
oiooj
oioij
oioij

2 2 2 1

-1

Bajtazar oraz jego N przyjaciele mieszkają na tej samej prostej ulicy i trenują do Olimpiady Informatycznej Juniorów. Przez brak światłowodu, narzekają oni na słaby internet, więc Bajtazar postanowił wybudować wzmacniacz sygnału internetu przy ich drodze.

Bajtazar wie, że jego i-ty przyjaciel znajduje się początkowo w swoim domu, D_i metrów od początku ulicy i jest w stanie przejść jeden metr w P_i sekund w dowolnym kierunku. Przyjaciel ten posiada laptop, który pozwoli mu połączyć się ze wzmacniaczem, jeśli znajdzie się on w odległości co najwyżej Z_i od wzmacniacza. Zarówno na początku (niektórzy przyjaciele to rodzeństwo i mieszkają w tym samym domu), jak i podczas ruszania się, kilka osób może się znajdować na tej samej pozycji na ulicy.

Po tym, jak Bajtazar wybierze liczbę całkowitą w i wybuduje wzmacniacz w odległości w metrów od początku ulicy, wyśle wiadomość o nim do wszystkich swoich przyjaciół. Wtedy każdy z przyjaciół zacznie iść wzdłuż ulicy przez minimalną ilość czasu, która pozwoli mu znaleźć się w zasięgu wzmacniacza (innymi słowy, dopóki przyjaciel numer i znajdzie się co najwyżej Z_i metrów od w).

Bajtazar chciałby się dowiedzieć, jaka jest najmniejsza możliwa suma czasów, przez którą jego N przyjaciele będą musieli się poruszać, przy optymalnym wyborze w. Nie umie on jednak znaleźć odpowiedzi samemu, więc poprosił Cię o pomoc.

Wejście

W pierwszym wierszu wejścia znajduje się jedna liczba całkowita N – liczba przyjaciół Bajtazara.

W każdym z kolejnych N wierszy znajdują się trzy liczby całkowite oddzielone pojedynczymi spacjami: D_i, P_i, Z_i. Są to odpowiednio: pozycja domu, czas przejścia jednego metra oraz zasięg i-tego przyjaciela.

Wyjście

W pierwszym i jedynym wierszu wyjścia powinna znaleźć się jedna liczba całkowita – minimalny sumaryczny czas, który przyjaciele Bajtazara spędzą na znalezienie się w zasięgu wzmacniacza.

Ograniczenia

1 ≤ N ≤ 200 000.

0 ≤ D_i ≤ 10⁹.

1 ≤ P_i ≤ 1 000.

0 ≤ Z_i ≤ 10⁹.

Podzadania

Przykład

1
0 1000 0

0

2
10 4 3
20 4 2

20

3
6 8 3
1 4 1
14 5 2

43

Bajtazar pracuje nad nowym systemem wyszukiwanai plików i eksperymentuje z dopasowywaniem wzorców. Aktualnie posiada zestaw N wzorców P₁, P₂, …, P_N. Każdy wzorzec opisuje napisy, które do niego pasują. Teraz chce sprawdzić, czy da się znaleźć jeden napis pasujący do wszystkich wzorców.

Wzorzec składa się z co najmniej jednego znaku specjalnego * i może (ale nie musi) zawierać wielkie litery alfabetu angielskiego.

Mówimy, że napis S pasuje do wzorca P, jeśli można zastąpić każdą gwiazdkę * w P pewnym ciągiem (być może pustym) wielkich liter tak, aby po tych podstawieniach otrzymać dokładnie napis S.

Wzorzec A*B pasuje do: AB, AXB, ABJB, AHELLOB.

Wzorzec *ABC* pasuje do: ABC, ZABCQ, HELLOABC.

Wzorzec AB*CD nie pasuje do: ABDC, ABCDX.

Bajtazar zastanawia się, czy istnieje taki napis S (składający się wyłącznie z wielkich liter alfabetu angielskiego), który pasuje do wszystkich N wzorców jednocześnie oraz nie przekracza długości 10 000 znaków.

Jeśli taki napis istnieje, należy wypisać dowolny z nich. Jeżeli nie istnieje żaden napis spełniający powyższych wymagań, należy wypisać *.

Wejście

W pierwszym wierszu wejścia znajduje się jedna liczba całkowita T - liczba zestawów danych. Następnie podawane są opisy T zestawów danych.

Pierwszy wiersz każdego zestawu zawiera jedną liczbę całkowitą N – liczbę wzorców. W kolejnych N wierszach znajdują się wzorce P₁, P₂, …, P_N. Każdy wzorzec jest ciągiem znaków składającym się z wielkich liter alfabetu angielskiego oraz gwiazdek (*).

Wyjście

Dla każdego zestawu danych wypisz w osobnym wierszu odpowiedni napis o długości co najwyżej 10 000 znaków.

Jeżeli nie istnieje żaden napis spełniający powyższych wymagań, należy wypisać *.

Ograniczenia

1 ≤ T ≤ 100

2 ≤ N ≤ 50

2 ≤ |P_i| ≤ 100

Każdy wzorzec zawiera co najmniej jedną gwiazdkę.

Podzadania

Przykład

2
5
*CONUTS
*COCONUTS
*OCONUTS
*CONUTS
*S
2
*XZ
*XYZ

COCONUTS
*