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 does'nt exist print "-1".

Input

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

Line 2: no. 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