As the cross country running competition date approaches, Jonathan is practicing harder than ever for his race.

Near his house, there is a long track that can be represented as a chain of ~N~ ~(1 \le N \le 10^3)~ continuous segments of road, numbered from ~1~ to ~N~. Each segment of road is initially ~R_i~ ~(1 \le R_i \le 10^3)~ metres long - however, as the City of Toronto is notorious for its frequent constructions, the length of specific roads may change over the next few days.

When Jonathan decides to practice, he will choose a starting position at the beginning of one of these roads and will continue running forward as far as can under the limit of his lung capacity, ~C~ ~(1 \le C \le 10^3)~, where ~C~ is in meters. That is, he will run continuous meters either until adding the next segment of road would exceed ~C~ or if he finishes the ~N~th road. Additionally, after each practice, his lung capacity will increase by ~I~ ~(1 \le I \le 10^3)~ meters.

Besides just running practice, though, intense cross country also calls for one to own a ridiculous collection of shoes. It is rumored that depending on the shoe that one is wearing, the runner's lung capacity may even increase! Jonathan has a collection of ~X~ ~(2 \le X \le 10)~ shoes, each of which provides him with an extra ~E_i~ ~(1 \le E_i \le 10^3)~ running capacity. Note that this is not a permanent increase to his lung capacity - it is merely an add-on. By default, Jonathan will wear his ~1~st pair of shoes.

Over the course of the next ~M~ ~(1 \le M \le 10^3)~ days, one of three events can occur: A segment of road's length is updated, Jonathan goes for a run, or Jonathan switches his shoes.

More specifically, there will be three types of queries:

• 1 x y The ~x~th ~(1 \le x \le N)~ segment of road has its length updated to ~y~ ~(1 \le y \le 10^3)~ meters.
• 2 L Jonathan goes for a run starting from the ~L~th segment of road.
• 3 x Jonathan switches his current pair of shoes for the ~x~th pair.

For every type 2 query, print out the longest length in meters that he can run.

Constraints

~1 \le N, M, I, R_i, C, E_i \le 10^3~

~2 \le X \le 10~

For every type 3 query, it is guaranteed that the new pair of shoes Jonathan switches to is different from his previous pair.

Input Specification

The first line will contain ~N~, ~M~, ~C~, ~X~, ~I~, space-separated.

The next line will contain ~N~ integers ~R_i~ ~(1 \le i \le N)~, the length of each road.

The next line will contain ~X~ integers ~E_i~ ~(1 \le i \le X)~, the boost of each pair of shoes.

The next ~M~ lines will contain a query of the form defined above.

Output Specification

For every type 2 query, print out the longest length in meters that he can run on its own line.

Sample Input 1

5 10 15 3 3
8 5 3 4 10
2 6 5
3 2
2 2
3 3
2 1
2 2
1 3 10
2 3
3 1
1 4 3
3 2

Sample Output 1

12
20
22
24

Sample 1 Explanation

Initially, Jonathan's running capability is ~C + E[1] = 15 + 2 = 17~. After switching his shoes to the ~2~nd pair, his running capability is ~C + E[2] = 15 + 6 = 21~. For his first practice, he can run up to ~5 + 3 + 4 = 12~ meters. Note that if he tries running the next segment, the total length will be ~5 + 3 + 4 + 10 = 22~ meters, and since ~22 > 21~, he can't run that length.