Description
潘多拉星球上的树按照1~n进行编号，按照下面规则每天进行一次维护：

每次维护前选出最高的树和最矮的树，如果高度相同，编号小的更矮，编号大的更高；

按照编号，每次维护最矮的树和最高的树之间所有的树，为了保证所有树高度差距不大,最高的树不需要维护，最矮的需要维护；

每棵树每次维护能让增长h米。

Na'vi人准备花m天的时间维护，请计算出每次维护后最矮树和最高树的编号和高度。

Format
Input
第一行：3个整数，n、m、h，分别表示潘多拉星球树的数量n，维护的天数m，每次维护能让树增长的高度；

第二行：n个整数，第i个数表示编号为i的树的初始高度high[i]。

2≤n,m≤1000000 h≤1000 high[i] ≤10000

Output
m行，每行4个整数，用一个空格隔开。表示每次维护后，最矮树的编号和高度，最高树的编号和高度。

Samples
输入数据 1
5 10 2
1 2 3 4 5
输出数据 1
1 3 4 6
1 5 3 7
5 5 2 8
1 7 3 9
5 7 2 10
1 9 3 11
5 9 2 12
1 11 3 13
5 11 2 14
1 13 3 15
Hint

样例说明：

第1次维护1-4，维护后为:3 4 5 6 5

第2次维护1-4，维护后为:5 6 7 6 5

第3次维护1-3，维护后为:7 8 7 6 5

第4次维护3-5，维护后为:7 8 9 8 7

第5次维护1-2，维护后为:9 10 9 8 7

第6次维护3-5，维护后为:9 10 11 10 9

第7次维护1-2，维护后为:11 12 11 10 9

第8次维护3-5，维护后为:11 12 13 12 11

第9次维护1-2，维护后为:13 14 13 12 11

第10次维护3-5，维护后为:13 14 15 14 13

#include <bits/stdc++.h>
#define ll long long
using namespace std;
int a[10000001],n,m,h,minn[10000001],maxx[10000001],ansmax,ansmin,idm,idn,mxi[10000001],mii[10000001];
void bui(int id,int l,int r)
{
  if(l == r)//左端点等于右端点，即为叶子节点(区间长度为1)，直接赋值即可
  {
    maxx[id] = a[l];
    minn[id] = a[l];
    mxi[id] = l;
    mii[id] = l;
    return ;
  }
// 否则将当前区间中间拆开成两个区间
  int mid = (l + r) / 2;//mid则为中间点，左儿子的结点区间为[l,mid],右儿子的结点区间为[mid + 1,r]
  bui(id * 2,l,mid); //递归构造左儿子结点
  bui(id * 2 + 1,mid + 1,r); //递归构造右儿子结点
// 左右两个区间计算完成以后
// 合并到当前区间
  if(maxx[id * 2] > maxx[id * 2 + 1]) mxi[id] = mxi[id * 2];
  else mxi[id] = mxi[id * 2 + 1];
  if(minn[id * 2] <= minn[id * 2 + 1]) mii[id] = mii[id * 2];
  else mii[id] = mii[id * 2 + 1];
  maxx[id] = max(maxx[id * 2],maxx[id * 2 + 1]);//更新父节点
  minn[id] = min(minn[id * 2],minn[id * 2 + 1]);
}
//id 表示树节点编号，l r 表示这个节点所对应的区间
//x y表示查询的区间
void find(int id,int l,int r,int x,int y)
{
  //需要查询的区间[x,y]将当前区间[l,r]包含的时候
  if(x <= l && r <= y)
  {
    if(maxx[id] >= ansmax)
    {
      ansmax = maxx[id];
      idm = mxi[id];
    }
    if(minn[id] < ansmin)
    {
      ansmin = minn[id];
      idn = mii[id];
    }
    return ;
  }
  int mid = (l + r) / 2;
  if(x <= mid) find(id * 2,l,mid,x,y);
  if(y > mid) find(id * 2 + 1,mid + 1,r,x,y);
}
void gexi(int id, int l, int r, int x, int y,int v)
{
  if(l == r)
  {
    maxx[id] += v;
    minn[id] += v;
    return;
  }
  int mid = (l + r) / 2;
  if(x <= mid) gexi(id * 2, l, mid, x,y, v);
  if(y > mid) gexi(id * 2 + 1, mid + 1, r, x,y, v);
  if(maxx[id * 2] > maxx[id * 2 + 1]) mxi[id] = mxi[id * 2];
  else mxi[id] = mxi[id * 2 + 1];
  if(minn[id * 2] <= minn[id * 2 + 1]) mii[id] = mii[id * 2];
  else mii[id] = mii[id * 2 + 1];
  maxx[id] = max(maxx[id * 2], maxx[id * 2 + 1]);
  minn[id] = min(minn[id * 2], minn[id * 2 + 1]);
}

signed main()
{
  cin>>n>>m>>h;
  for(int i = 1; i <= n; i++) scanf("%d",&a[i]);
  bui(1,1,n);
  while(m--)
  {
    ansmax = -INT_MAX;
    ansmin = INT_MAX;
    idn = 0;
    idm = 0;
    find(1,1,n,1,n);
    //printf("%d %d %d %d\n",idn,ansmin,idm,ansmax);
    gexi(1,1,n,idn,idm - 1,h);
    ansmax = -INT_MAX;
    ansmin = INT_MAX;
    idn = 0;
    idm = 0;
    find(1,1,n,1,n);
    printf("%d %d %d %d\n",idn,ansmin,idm,ansmax);
//    for(int i = 1; i <= n; i++)
//    {
//      ansmax = -INT_MAX;
//      ansmin = INT_MAX;
//      find(1,1,n,i,i);
//      cout<<ansmin<<' ' ;
//    }
    cout<<'\n';
  }
  return 0;
}

样例都没过