Tom has a string containing only lowercase letters. He wants to choose a subsequence of the string whose length is kk 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 iith letter from a to z (indexed from 11 to 2626) must in [Li,Ri][Li,Ri]. 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|≤105)S(|S|≤105)and an integer k(1≤k≤|S|)k(1≤k≤|S|). Then 2626 lines follow, each line two numbers Li,Ri(0≤Li≤Ri≤|S|)Li,Ri(0≤Li≤Ri≤|S|). It's guaranteed that SS consists of only lowercase letters, and ∑|S|≤3×105∑|S|≤3×105.
Output
Output the answer string. If it doesn't exist, output −1−1.