Consider integer sequence *a*<sub class="lower-index">1</sub>, *a*<sub class="lower-index">2</sub>, ..., *a*<sub class="lower-index">*n*</sub>. You should run queries of two types:
 -  The query format is "0 *i* *val*". In reply to this query you should make the following assignment: *a*<sub class="lower-index">*i*</sub> = *val*. -  The query format is "1 *l* *r* *k*". In reply to this query you should print the maximum sum of at most *k* non-intersecting subsegments of sequence *a*<sub class="lower-index">*l*</sub>, *a*<sub class="lower-index">*l* + 1</sub>, ..., *a*<sub class="lower-index">*r*</sub>. Formally, you should choose at most *k* pairs of integers (*x*<sub class="lower-index">1</sub>, *y*<sub class="lower-index">1</sub>), (*x*<sub class="lower-index">2</sub>, *y*<sub class="lower-index">2</sub>), ..., (*x*<sub class="lower-index">*t*</sub>, *y*<sub class="lower-index">*t*</sub>) (*l* ≤ *x*<sub class="lower-index">1</sub> ≤ *y*<sub class="lower-index">1</sub> &lt; *x*<sub class="lower-index">2</sub> ≤ *y*<sub class="lower-index">2</sub> &lt; ... &lt; *x*<sub class="lower-index">*t*</sub> ≤ *y*<sub class="lower-index">*t*</sub> ≤ *r*; *t* ≤ *k*) such that the sum *a*<sub class="lower-index">*x*<sub class="lower-index">1</sub></sub> + *a*<sub class="lower-index">*x*<sub class="lower-index">1</sub> + 1</sub> + ... + *a*<sub class="lower-index">*y*<sub class="lower-index">1</sub></sub> + *a*<sub class="lower-index">*x*<sub class="lower-index">2</sub></sub> + *a*<sub class="lower-index">*x*<sub class="lower-index">2</sub> + 1</sub> + ... + *a*<sub class="lower-index">*y*<sub class="lower-index">2</sub></sub> + ... + *a*<sub class="lower-index">*x*<sub class="lower-index">*t*</sub></sub> + *a*<sub class="lower-index">*x*<sub class="lower-index">*t*</sub> + 1</sub> + ... + *a*<sub class="lower-index">*y*<sub class="lower-index">*t*</sub></sub> is as large as possible. Note that you should choose at most *k* subsegments. Particularly, you can choose 0 subsegments. In this case the described sum considered equal to zero.
The first line contains integer *n* (1 ≤ *n* ≤ 10<sup class="upper-index">5</sup>), showing how many numbers the sequence has. The next line contains *n* integers *a*<sub class="lower-index">1</sub>, *a*<sub class="lower-index">2</sub>, ..., *a*<sub class="lower-index">*n*</sub> (|*a*<sub class="lower-index">*i*</sub>| ≤ 500). 

The third line contains integer *m* (1 ≤ *m* ≤ 10<sup class="upper-index">5</sup>) — the number of queries. The next *m* lines contain the queries in the format, given in the statement.

All changing queries fit into limits: 1 ≤ *i* ≤ *n*, |*val*| ≤ 500.

All queries to count the maximum sum of at most *k* non-intersecting subsegments fit into limits: 1 ≤ *l* ≤ *r* ≤ *n*, 1 ≤ *k* ≤ 20. It is guaranteed that the number of the queries to count the maximum sum of at most *k* non-intersecting subsegments doesn't exceed 10000.
line = raw_input().split()
n, l = int(line[0]), int(line[1])*10e10
lan = [int(x)*10e10 for x in raw_input().split()]

lan.sort()

# print lan

def check(d):
  if lan[0]-d > 0 or lan[n-1]+d < l:
    return False

  if n == 2 and (lan[n-1]-d > lan[0]+d):
    return False

  for i in xrange(1, n-1):
    if lan[i]-d > lan[i-1]+d or lan[i+1]-d > lan[i]+d:
      return False

  return True


low, high = 0, l
while high-low > 1:
  mid = (high+low)/2
  print high, low

  if check(mid):
    high = mid;
  else:
    low = mid + 1;

print high/10e10

	 	     	    	    	   		 		 			