On the planet of Royal Royal, a university named Royal University of Engineering and Technology exists for the educational nurturing of aliens from different planets. Currently, there are N aliens residing in the university. Since they are from different planets, their year systems are different too.
In each and every planet, there is no concept of month. There are only years. On the planet of the ith alien, a year consists of Yi days. The birthday of the ith alien is the Dith day of the year in his/her planet. So, D5 = 2 and Y5 = 7 means that on the planet of the 5th alien, a year consists of 7 days, and the 2nd day of the year there is the birthday of the 5th alien.
Being the CR of Royal University of Engineering and Technology, your job is to arrange the birthdays of the aliens. But both you and the university does not want to spend much money on the alien students. So you have decided to find a common day for arranging the birthdays of all the aliens. Fortunately, all the days in all the planets have the same duration and the days start and end at the same time. Also, the day-year counting system started at the same time in all the planets i.e. the first days of the first years in all the planets began at the same time. The only difference in the planets is the number of days in a year. In Royal Royal planet itself, today is the Eth day of the Fth year and each year of Royal Royal planet consists of 10 days only.
With all these in mind, you need to solve the following problem of 2 types of operations:
The first type of operation is given as 1 i A B as input. It implies that the birthday and number of days in year information is updated for the ith alien i.e. Di = A and Yi = B from now on.
The second type of operation is given as 2 L R in input, implying that you have to find the closest common birthday in the future of all the aliens from L to R range and print that day in the year system of Royal Royal planet. In other words, you have to find the Gth day of the Hth year in the Royal Royal planet such that this day is the birthday of all the ith alien where L ≤ i ≤ R. Note that this common birthday must come strictly after today.
Input
Input starts with a line containing four space-separated integers N, Q, E and F - the number of aliens, the number of operations, the current day and the current year in Royal Royal planet respectively.
The following line consists of N space-separated integers, the ith of these numbers Di represents the birthday of the ith alien in his own planet.
The next line consists N space-separated integers, the ith of these numbers Yi represents the number of days in a year in the planet of the ith alien.
Each of the next Q lines can be in any of the 2 following formats, specifying the operations as described before.$ \cdot $ 1 i A B$ \cdot $ 2 L R
Constraints
1 ≤ N, Q ≤ 105
1 ≤ Yi, B ≤ 40
1 ≤ Di ≤ Yi
1 ≤ i ≤ N
1 ≤ A ≤ B
1 ≤ L ≤ R ≤ N
1 ≤ A ≤ B
1 ≤ F ≤ 109
1 ≤ E ≤ 10
Output
For each operation of the second type, print G H separated by a single space in a single line as shown in sample I/O.
If a solution does not exist for an operation, print -1 for that line.
Samples
| Input | Output |
|---|---|
3 8 1 1 2 5 6 3 5 7 2 1 3 2 1 2 1 3 7 7 2 1 3 1 1 6 7 2 1 3 2 1 1 2 2 3 | 10 2 5 1 5 4 -1 6 1 5 4 |
There are 3 aliens. In the planet of the first alien, a year consists of 3 days and the 2nd day of the year in that planet is the birthday of the first alien. The first operation is | |
| Input | Output |
|---|---|
4 6 1 1 1 1 4 5 3 5 7 8 2 1 2 2 1 3 1 2 1 7 2 1 4 1 3 1 7 2 1 3 | 6 2 6 5 -1 2 3 |
