D. Switching To Windows
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Uncle Eyad is a Linux creep and his friend Jaber has always begged him to switch to Windows and he finally did!! Eyad works for the uncleship company owned and managed by his boss Hosen the grand uncle, and he is in control of the company's database system. Hosen usually gives Eyad queries to the database, and Eyad usually responds to them and maintains the database easily using Linux, but not anymore!!

As a good friend of Eyad, he asked you to help him respond to Hosen's queries and maintain the database accordingly.

Initially, the database is empty, Hosen gives Eyad $$$Q$$$ uncly queries one by one, and the queries have $$$5$$$ different types as described in the following:

  • $$$1$$$ $$$S$$$ $$$V$$$ : Add a string $$$S$$$ whose value is $$$V$$$ to the database.
  • $$$2$$$ $$$i$$$ : Erase the string added in the $$$i$$$-th query from the database. It is guaranteed that the $$$i$$$-th query was of the first type and that the string is currently in the database.
  • $$$3$$$ $$$L$$$ $$$R$$$ $$$x$$$ : For each string in the database that was added in the $$$i$$$-th query $$$(L \le i \le R)$$$, change its value to $$$x$$$.
  • $$$4$$$ $$$L$$$ $$$R$$$ $$$x$$$ : For each string in the database that was added in the $$$i$$$-th query $$$(L \le i \le R)$$$, increase its value by an amount of $$$x$$$.
  • $$$5$$$ $$$S$$$ $$$L$$$ $$$R$$$ : Output the number of substrings in $$$S$$$ which are currently in the database and have a value $$$V$$$ $$$(L \le V \le R)$$$. The substrings are not necessarily distinct.
Input

The first line contains a single integer number $$$Q$$$ $$$(1 \le Q \le 2 * 10^5)$$$. The following $$$Q$$$ lines contain the description of the queries in the previous format in the problem statement.

  • $$$1$$$ $$$S$$$ $$$V$$$ : $$$(1 \le V \le 10^{18})$$$.
  • $$$2$$$ $$$i$$$ : $$$(1 \le i \le 2 * 10^5)$$$.
  • $$$3$$$ $$$L$$$ $$$R$$$ $$$x$$$ : $$$(1 \le L, R \le 2 * 10^5)$$$, $$$(1 \le x \le 10^{18})$$$.
  • $$$4$$$ $$$L$$$ $$$R$$$ $$$x$$$ : $$$(1 \le L, R \le 2 * 10^5)$$$, $$$(1 \le x \le 10^9)$$$.
  • $$$5$$$ $$$S$$$ $$$L$$$ $$$R$$$ : $$$(1 \le L, R \le 10^{18})$$$.
It is guaranteed that the sum of lengths of all strings in the input does not exceed $$$2 * 10^5$$$, and all the strings given in the input in the first type query are distinct, and it is guaranteed that the first query is a first-type query.
Output

For each query of the $$$5$$$-th type, output the answer to it.

Example
Input
13
1 a 3
1 b 6
1 ab 5
1 ca 2
1 ac 10
1 aba 1
5 caba 3 6
2 2
5 caba 3 6
3 1 4 2
5 caba 3 6
4 6 6 5
5 caba 3 6
Output
4
3
0
1