Од неодамна Трпе е вработен во еден скопски магацин. Една од неговите задачи е да нареди неколку кутии една врз друга, за тие да зафаќаат помалку простор во магацинот. Кутиите имаат разни тежини, и секоја од нив содржи одредена стока. Бидејќи некои кутии треба да се отвораат почесто (содржат поважна стока), одредени кутии треба и мора да се поставени врз други кутии. Бидејќи Трпе е мрзлив, му треба вашата помош да пресмета во кој редослед треба да ги постави кутиите (една врз друга), така што за поставувањето би му требало најмалку напор од негова страна.

За поставување на најдолната кутија не треба никаков напор. За поставување на сите останати кутии треба w*h напор, каде што w ја претставува тежината на кутијата, а h e бројот на кутии досега поставени. Можете да претпоставите дека сите кутии се коцки со еднакви димензии.

Влез

Во првиот ред е запишан еден цел број N (2 <= N <= 8), кој го означува бројот на кутии. Во вториот ред се запишани тежините Wi (1 <= Wi <= 1000) на секоја од N-те кутии. Во третиот ред е запишан еден цел број D (0 <= D <= 64), кој го означува бројот на ограничувања. Во секој од следните D редови се запишани по два цели броја Ai и Bi (1 <= Ai, Bi <= N), кои означуваат дека кутијата со индекс Ai мора да се наоѓа над кутијата со индекс Bi (немора да биде веднаш над таа кутија). Индексите почнуваат од 1 (кутијата чија тежина е дадена прва во вториот ред од влезот има индекс 1, кутијата чија тежина е дадена втора има индекс 2, итн...)

Излез

На стандарден излез отпечатете го редоследот на кутиите (нивните индекси, почнувајќи од кутијата која што треба да се постави најдолу), така што за нивното поставување во магацинот би требало најмалку напор. Доколку постојат повеќе такви редоследи, отпечатете го оној каде најдолната кутија има најмал индекс. Доколку сеуште има повеќе редоследи, отпечатете го оној каде 2-рата кутија од долу има најмал индекс, итн..

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

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

Примери

влез
3
10 1 1000
1
3 2

излез
2 3 1