Zing was his senior crush. In order to get impressed, she gave him the following problem:

A string is given as input in lowercase. There are two types of queries:

• Type 1: 0 l r c  (update the string with character 'c' from 'l' to 'r').
• Type 2: 1 k c (Print the index of kth character 'c').

If the k'th character doesn't exist print "-1".

Input

Line 1: string input (1<=length<=100000)

Line 2: number of queries (<=100000)

In next q lines, the queries of type 1 and type 2 are given.

Output

For each print query, print the integer index or "-1".

Example

Input:
zazzxeffah
3
1 3 z
0 2 4 a
1 3 z

Output:
4
-1