Blobs, a renowned painter from Flower Town is about to have a solo show at the local art gallery. He presented \textbf{k}works to be exhibited but unfortunately the gallery has only \textbf{n} exhibit spaces. Each exhibit space is a wall-mounted painting holder. During preparations it turned out that the holders are designed for paintings of different weight. Holder number \textbf{i} can carry an exhibit weighting no more than \textbf{d_i} grams. As it is impossible to display all the works anyway, Blobs estimated the artistic value \textbf{a_i} of each painting. He also weighted all of them to know the weights \textbf{w_i} (in grams). Please help Blobs in selecting a set of paintings to be displayed, maximizing the total artistic value. Write a program that will map the set of paintings having the maximum total artistic value to the available exhibit spaces. If several optimal solutions exist, any of them will be accepted as correct. \InputFile The first line of the input file contains two space-delimited integers \textbf{n} and \textbf{k} (\textbf{1} ≤ \textbf{n} ≤ \textbf{k} ≤ \textbf{10000}). The second line contains \textbf{n} space-delimited integers describing maximum loads for holders: \textbf{d_1}, \textbf{d_2}, \textbf{d_3}, … \textbf{d_n}. Then \textbf{k} lines follow, with two space-delimited numbers each: \textbf{a_j} and \textbf{w_j}, the artistic value and the weight of the \textbf{j}-th painting. The paintings are listed in ascending order of numbers: the third line of input contains \textbf{a_1}, \textbf{w_1}, the fourth -- \textbf{a_2}, \textbf{w_2}, the fifth -- \textbf{a_3}, \textbf{w_3}, and so on (\textbf{1} ≤ \textbf{a_i}, \textbf{d_j}, \textbf{w_j} ≤ \textbf{1000000}, \textbf{1} ≤ \textbf{i} ≤ \textbf{n}, \textbf{1} ≤ \textbf{j} ≤ \textbf{k}). \OutputFile The output file should contain \textbf{n} integers separated with spaces --- the numbers of paintings to be placed in corresponding exhibit spaces. Here, the number in position i is the number of painting to be displayed in the exhibit space \textbf{i}. If an exhibit space is empty then output \textbf{0} in the corresponding position.