提示: 欢迎访问OurACM平台。
Problem 1961 凯撒密码II

Accept: 265    Submit: 681
Time Limit: 2000 mSec    Memory Limit : 32768 KB

Problem Description

在人类历史上,对信息保护的需求与对信息本身的需求一样久远。第一个用于加密和解密文本的编码方式是凯撒密码。由于原始的凯撒密码较简单,较易被破解。随着考古的进展,人们发现了升级版的凯撒密码II。

凯撒密码II通过查询动态密码表,把凯撒单词加密成一些密文数字。

现在请你使用现有动态密码表,加密一些单词。你要处理m个操作,操作分成两种:

A string integer: 增加一条凯撒单词string到凯撒密文数字integer的映射规则,如果先前已经有关于这个string的规则,那么用该规则替换原规则。

Q string: 查询单词string所对应的最新密文数字。

Input

第一行一个整数m(1<= m<=1,000,000),表示有m个操作。

单词仅有长度不超过8位的小写字母组成,单词总数不超过100,000个。

密文数字的范围是[0..1,000,000,000]。

Output

对于每组查询,输出一行,表示根据密码表中的规则,加密后的密文数字,如果在无法在密码表中查找到该单词,输出 -1。

Sample Input

7 A aaab 10 A aaac 20 A aaad 30 Q aaac A aaac 40 Q aaaa Q aaac

Sample Output

20 -1 40

Source

Contest for 2010 lecture I

Submit  Back  Status  Discuss