Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

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 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**

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

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.

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 |

Toph uses cookies. By continuing you agree to our Cookie Policy.