Fafa has an array A of n positive integers, the function f ( A ) is defined as . He wants to do q queries of two types: 1 l r x — find the maximum possible value of f ( A ) , if x is to be added to one element in the range l , r . You can choose to which element to add x . 2 l r x — increase all the elements in the range l , r by value x . Note that queries of type 1 don't affect the array elements. The first line contains one integer n (3 ≤ n ≤ 10 5 ) — the length of the array. The second line contains n positive integers a 1 , a 2 , ..., a n (0 < a i ≤ 10 9 ) — the array elements. The third line contains an integer q (1 ≤ q ≤ 10 5 ) — the number of queries. Then q lines follow, line i describes the i -th query and contains four integers t i l i r i x i . It is guaranteed that at least one of the queries is of type 1 . For each query of type 1 , print the answer to the query.