{"problem":{"name":"[ICPC 2024 Xi'an I] Rubbish Sorting","description":{"content":" Bob has many pieces of rubbish. One day, he wants to sort them.                For every piece of rubbish, its type is expressed as a positive integer.                He has $q$ operations. For each ","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":2000,"memory_limit":1048576},"difficulty":{"LuoguStyle":"P4"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP10564"},"statements":[{"statement_type":"Markdown","content":"Bob has many pieces of rubbish. One day, he wants to sort them.\n    \n    \n    \nFor every piece of rubbish, its type is expressed as a positive integer.\n    \n    \n    \nHe has $q$ operations. For each operation, it is one of the following two operations.\n\n- `1 s x` He tells you that the piece of rubbish named $s$ has a type of $x$.\n- `2 s` He wants to ask you the type of rubbish $s$.\n\n    \nBut his memories are not always accurate.\n    \n    \n    \nFor each operation $2$, $s$ may not have appeared in the previous operation $1$s.\n    \n    \n    \nWe define the similarity of two strings $s_1$ and $s_2$ as $\\sum_{i=1}^{\\min\\{|s_1|,|s_2|\\}} [s_{1,i}=s_{2,i}]$.\n    \n    \n    \nHere all the strings' indexes start at $1$.\n    \n    \n    \nFor a string $s$, its type is the type of string which has the maximum similarity to $s$ among all the strings that have appeared in the previous operations $1$s. Note that if there are multiple strings that all have the maximum similarity to $s$, the type of $s$ is the minimum type of these strings' type.\n    \n    \n    \nNow, he wants you to solve this problem.\n    \n\n## Input\n\nThe first line contains an integer $q(1\\le q\\le 3\\times 10^5)$, which is the number of operations.\n    \n    \n    \nNext $q$ lines contain operations, one per line. They correspond to the description given in the statement.\n    \n    \n    \nIt is guaranteed that for every operation $2$ there is at least one operation $1$ before it.\n    \n    \n    \nBut some pieces of rubbish will have more than one type, you can consider it as the minimum type you have read.\n    \n    \n    \nThe rubbish's names only consist of lowercase Latin letters.\n    \n    \n    \n$1 \\le |s| \\le 5, 1 \\le x \\le 10^9$\n\n## Output\n\n    \nFor every operation $2$, you should print an integer in a single line that is the rubbish $s$'s type.\n    \n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"LGP10564","tags":["2024","O2优化","ICPC","西安"],"sample_group":[["4\n1 aaa 1\n2 aa\n1 ab 2\n2 bb","1\n2"]],"created_at":"2026-03-03 11:09:25"}}