ZING01 - Impress zing

no tags 

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

hide comments
nadstratosfer: 2019-01-27 16:19:15

Psetter, any idea what happened to your other problem a week ago? The ranking is accessible at https://www.spoj.com/ranks/ZING02/ , but the problem page itself doesn't exist anymore.


Added by:zing
Date:2018-09-22
Time limit:1s-2s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All