H. Ammar-utiful Array
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Ammar does not know how to set problems. Therefore, Coach Khaled felt pitty about Ammar and decided to put his name on one of his problems, which is this problem.

We define an array of $$$M$$$ integers to be called an Ammar-utiful Array of Ammar-uty $$$X$$$ if the sum of all of its elements is less than or equal to $$$X$$$.

Ammar will give you $$$N$$$ elements, such that each element $$$i$$$ is associated with value $$$A_i$$$ and color $$$C_i$$$. You need to process $$$Q$$$ queries of the following forms:

  • $$$1 \; Col \; X$$$: For each element $$$i$$$ $$$(1 \le i \le N)$$$ such that $$$C_i \ne Col$$$, increase $$$A_i$$$ by $$$X$$$.
  • $$$2 \; Col \; Y$$$: Consider an array $$$B$$$ that consists of elements with color equal to $$$Col$$$, in the same original order that they appeared in array $$$A$$$. What is the length of the longest prefix $$$P$$$ (the prefix can be empty) of $$$B$$$ such that $$$P$$$ is an Ammar-utiful Array of Ammar-uty $$$Y$$$. (It is guaranteed that there is at least one element whose color is equal to $$$Col$$$).
Input

The first line of the input contains two integers $$$N$$$ $$$(1 \le N \le 2\cdot 10^5)$$$.

The second line of the input contains $$$N$$$ space-separated integers $$$A_1, A_2, \cdots, A_N$$$ $$$(1 \le A_i \le 2 \cdot 10^5)$$$ — the values associated with the elements.

The third line of the input contains $$$N$$$ space-separated integers $$$C_1, C_2, \cdots, C_N$$$ $$$(1 \le C_i \le 2 \cdot 10^5)$$$ — the colors associated with the elements.

The next line of the input contains an integer $$$Q$$$ $$$(1 \le Q \le 2\cdot 10^5)$$$.

Each line of the next $$$Q$$$ lines contains three integers describing the queries.

  • $$$1 \; Col \; X$$$: $$$(1 \le Col \le 2\cdot 10^5)$$$ $$$(1 \le X \le 10^5)$$$ — the query of the first type.
  • $$$2 \; Col \; Y$$$: $$$(1 \le Col \le 2\cdot 10^5)$$$ $$$(1 \le Y \le 10^{15})$$$ — the query of the second type (It is guaranteed that there is at least one element whose color is equal to $$$Col$$$).
Output

For each query of the second type, print a single line containing the length of the longest prefix $$$P$$$ of $$$B$$$ such that $$$P$$$ is an Ammar-utiful Array of Ammar-uty Y.

Examples
Input
5
1 2 3 4 5
2 1 2 1 2
3
1 1 2
2 2 8
2 1 5
Output
2
1
Input
5
1 2 3 4 5
2 1 2 1 2
3
2 2 9
1 1 2
2 2 9
Output
3
2