Problem Description

Tom has a string containing only lowercase letters. He wants to choose a subsequence of the string whose length is $k$ and lexicographical order is the smallest. It's simple and he solved it with ease.
But Jerry, who likes to play with Tom, tells him that if he is able to find a lexicographically smallest subsequence satisfying following 26 constraints, he will not cause Tom trouble any more.
The constraints are: the number of occurrences of the $i$th letter from a to z (indexed from $1$ to $26$) must in $[L_i, R_i]$.
Tom gets dizzy, so he asks you for help.

Input

The input contains multiple test cases. Process until the end of file.
Each test case starts with a single line containing a string $S(|S|\le 10^5)$and an integer $k(1\le k\le |S|)$.
Then $26$ lines follow, each line two numbers $L_i,R_i(0\le L_i\le R_i\le |S|)$.
It's guaranteed that $S$ consists of only lowercase letters, and $\sum |S|\le 3\times 10^5$.

Output

Output the answer string.
If it doesn't exist, output $-1$.

aaabbb 3
0 3
2 3
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0

abb