Jonathan's Cross Country

View as PDF

Submit solution

Points: 10
Time limit: 2.0s
Memory limit: 256M

Problem type

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 Nth 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 1st 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 xth (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 Lth segment of road.
  • 3 x Jonathan switches his current pair of shoes for the xth pair.

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


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


Sample 1 Explanation

Initially, Jonathan's running capability is C + E[1] = 15 + 2 = 17. After switching his shoes to the 2nd 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.


There are no comments at the moment.