За пополнување на слободното време, Мендо, на големиот пазар во Радовиш, си купил нова игра. Играта, наречена "Пеонци", се игра на тркалезна плоча на која има N полиња (локации) за поставување на коцки. На почеток на играта, некои од полињата се обележани (пречкртани). Сите коцки се различни - на секоја коцка има напишано различен знак.

Накратко, играта се одвива на следниот начин:

    1. Прв чекор (позиционирање): Најпрвин, Мендо треба да одбере со колку (и кои) коцки ќе ја игра играта, да определи почетни полиња за коцките (на пример, коцката со знак 'A' на поле 6 [види слика], коцката со знак 'V' на поле 4, итн), и нив да ги постави на тие полиња (без да ги обележи). Почетните полиња мора да се иницијално необележани. На едно поле може да се постави најмногу една коцка. Почетните позиции (полиња) се паметат до крајот на играта.
    2. Втор чекор (влечење потези): Потег претставува преместување на една коцка (по избор на Мендо) P полиња во правец на движење на стрелките на часовникот. P може да биде еден од неколку однапред зададени цели броеви. Броевите се читаат од стандарден влез. Доколку полето кое се наоѓа точно P места од одбраното (во правец на движење на стрелките на часовникот) не е веќе обележано, тоа се обележува и коцката се поместува таму. Доколку полето е веќе обележано, потегот се смета за невалиден и се игнорира (коцката не се поместува). Доколку полето каде што сме ја преместиле коцката е почетната позиција на таа коцка, коцката се отстранува од плочата. Потези се влечат се додека постои начин да се поместуваат коцките.

Целта на Мендо е да определи со колку најмалку коцки може да се обележат сите полиња, а притоа, на крајот од играта, сите коцки да се отстранети од плочата. Напишете програма која ќе определи бараното. Уште еднаш: Една коцка се отстранува од играта кога таа, откако е поместена најмалку еднаш, ќе се врати на нејзината почетна позиција.

Влез

Во првиот ред е запишан еден цел број N (6 <= N <= 50), кој ја означува големината на плочата (од колку полиња е таа составена).

Во вториот ред се запишани точно N цели броеви Mi (0 <= Mi <= 1), кои означуваат кои полиња (Mi=1) се иницијално обележани (пред да започне играта). Ќе постои најмалку една позиција која не е иницијално обележана. Забележете дека, бидејќи плочата е тркалезна, последното поле (N) е соседно со првото (1). Полињата, на влез, се дадени во насока на движење на стрелките на часовникот.

Во третиот ред е запишан еден цел број K (1 <= K <= 6), кој го означува бројот на можни потези. Во четвртиот ред се запишани K цели броеви Pi (1 <= Pi <= 6), кои ги означуваат можните потези (колку полиња може да се премести една коцка во насока на движење на стрелките на часовникот). Броевите Pi се дадени во стриктно растечки редослед.

Забелешка: Во тест случаи кои вредат најмалку 30% од поените, ќе важи (6 <= N <= 8).

Излез

Излезот се состои од еден ред во кој треба да го отпечатите бараниот минимален број на коцки. Доколку не постои решение, отпечатете "GRESHKA".

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

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

Примери

влез
10
0 0 0 0 0 0 0 0 0 0
1
5

излез
5

влез
6
1 1 1 0 1 1
2
2 5

излез
GRESHKA

влез
6
0 0 0 0 0 0
1
5

излез
1

Објаснување за првиот пример: Доколку поставиме 5 коцки на првите 5 позиции, потребно е само да се направи еден круг со секоја од коцките (по две поместувања) за да се обележи целата плоча.

Објаснување за третиот пример: Доволна е само една коцка - иницијално поставена на било која позиција. Коцката ќе ги обележи сите полиња пред да се врати на својата почетна локација.