You are given two arrays, A and B, with N (1<=N<=10^5) elements each. You need to support Q (1<=Q<=10^5) queries:

TYPE 1: QUERY i j — query the maximum element with index from i to j

TYPE 2: UPDATE i j — for every k between i and j (inclusive) set a[k]=b[k]+a[k]

EXAMPLE:

A: 1 2 3 B: 6 9 1

QUERIES:

QUERY 1 3 -> 3 UPDATE 1 3 QUERY 1 3 -> 11

EXPLANATION:

After the update operation, A becomes 1+6 2+9 3+1 = 7 11 4. Maximum of this array is clearly 11.