Problem: <image>

It is well-known that the best decoration for a flower bed in Sweetland are vanilla muffins. Seedlings of this plant need sun to grow up. Slastyona has m seedlings, and the j-th seedling needs at least kj minutes of sunlight to grow up.

Most of the time it's sunny in Sweetland, but sometimes some caramel clouds come, the i-th of which will appear at time moment (minute) li and disappear at time moment ri. Of course, the clouds make shadows, and the seedlings can't grow when there is at least one cloud veiling the sun.

Slastyona wants to grow up her muffins as fast as possible. She has exactly C candies, which is the main currency in Sweetland. 

One can dispel any cloud by paying ci candies. However, in order to comply with Sweetland's Department of Meteorology regulations, one can't dispel more than two clouds.

Slastyona hasn't decided yet which of the m seedlings will be planted at the princess' garden, so she needs your help. For each seedling determine the earliest moment it can grow up if Slastyona won't break the law and won't spend more candies than she has. Note that each of the seedlings is considered independently.

The seedlings start to grow at time moment 0.

Input

The first line contains two integers n and C (0 ≤ n ≤ 3·105, 0 ≤ C ≤ 109) – the number of caramel clouds and the number of candies Slastyona has.

The next n lines contain three integers each: li, ri, ci (0 ≤ li < ri ≤ 109, 0 ≤ ci ≤ 109), describing one caramel cloud.

The next line contains single integer m (1 ≤ m ≤ 3·105) – the number of seedlings. Each of the seedlings is described with one integer kj (1 ≤ kj ≤ 109) – the required number of sunny minutes.

Output

For each seedling print one integer – the minimum minute Slastyona can grow it up.

Examples

Input

3 5
1 7 1
1 6 2
1 7 1
3
7
2
5


Output

12
7
10


Input

3 15
1 4 17
2 8 6
4 8 9
2
5
1


Output

8
1


Input

2 10
3 7 9
10 90 10
2
10
100


Output

10
104

Note

Consider the first example. For each k it is optimal to dispel clouds 1 and 3. Then the remaining cloud will give shadow on time segment [1..6]. So, intervals [0..1] and [6..inf) are sunny.

<image>

In the second example for k = 1 it is not necessary to dispel anything, and for k = 5 the best strategy is to dispel clouds 2 and 3. This adds an additional sunny segment [4..8], which together with [0..1] allows to grow up the muffin at the eight minute.

<image> <image>

If the third example the two seedlings are completely different. For the first one it is necessary to dispel cloud 1 and obtain a sunny segment [0..10]. However, the same strategy gives answer 180 for the second seedling. Instead, we can dispel cloud 2, to make segments [0..3] and [7..inf) sunny, and this allows up to shorten the time to 104.

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
const double pi = acos(0.0) * 2.0;
const long double eps = 1e-10;
const int step[8][2] = {{-1, 0}, {0, 1}, {1, 0},  {0, -1},
                        {-1, 1}, {1, 1}, {1, -1}, {-1, -1}};
template <class T>
inline T abs1(T a) {
  return a < 0 ? -a : a;
}
template <typename t, typename t1>
t min1(t a, t1 b) {
  return a < b ? a : b;
}
template <typename t, typename... arg>
t min1(t a, arg... arr) {
  return min1(a, min1(arr...));
}
template <typename t, typename t1>
t max1(t a, t1 b) {
  return a > b ? a : b;
}
template <typename t, typename... arg>
t max1(t a, arg... arr) {
  return max1(a, max1(arr...));
}
inline int jud(double a, double b) {
  if (abs(a) < eps && abs(b) < eps)
    return 0;
  else if (abs1(a - b) / max(abs1(a), abs1(b)) < eps)
    return 0;
  if (a < b) return -1;
  return 1;
}
template <typename t>
inline int jud(t a, t b) {
  if (a < b) return -1;
  if (a == b) return 0;
  return 1;
}
template <typename it, typename t1>
inline int find(t1 val, it a, int na, bool f_small = 1, bool f_lb = 1) {
  if (na == 0) return 0;
  int be = 0, en = na - 1;
  if (*a <= *(a + na - 1)) {
    if (f_lb == 0)
      while (be < en) {
        int mid = (be + en + 1) / 2;
        if (jud(*(a + mid), val) != 1)
          be = mid;
        else
          en = mid - 1;
      }
    else
      while (be < en) {
        int mid = (be + en) / 2;
        if (jud(*(a + mid), val) != -1)
          en = mid;
        else
          be = mid + 1;
      }
    if (f_small && jud(*(a + be), val) == 1) be--;
    if (!f_small && jud(*(a + be), val) == -1) be++;
  } else {
    if (f_lb)
      while (be < en) {
        int mid = (be + en + 1) / 2;
        if (jud(*(a + mid), val) != -1)
          be = mid;
        else
          en = mid - 1;
      }
    else
      while (be < en) {
        int mid = (be + en) / 2;
        if (jud(*(a + mid), val) != 1)
          en = mid;
        else
          be = mid + 1;
      }
    if (!f_small && jud(*(a + be), val) == -1) be--;
    if (f_small && jud(*(a + be), val) == 1) be++;
  }
  return be;
}
template <class T>
inline T lowb(T num) {
  return num & (-num);
}
inline int bitnum(unsigned int nValue) { return __builtin_popcount(nValue); }
inline int bitnum(int nValue) { return __builtin_popcount(nValue); }
inline int bitnum(unsigned long long nValue) {
  return __builtin_popcount(nValue) + __builtin_popcount(nValue >> 32);
}
inline int bitnum(long long nValue) {
  return __builtin_popcount(nValue) + __builtin_popcount(nValue >> 32);
}
inline int bitmaxl(unsigned int a) {
  if (a == 0) return 0;
  return 32 - __builtin_clz(a);
}
inline int bitmaxl(int a) {
  if (a == 0) return 0;
  return 32 - __builtin_clz(a);
}
inline int bitmaxl(unsigned long long a) {
  int temp = a >> 32;
  if (temp) return 32 - __builtin_clz(temp) + 32;
  return bitmaxl(int(a));
}
inline int bitmaxl(long long a) {
  int temp = a >> 32;
  if (temp) return 32 - __builtin_clz(temp) + 32;
  return bitmaxl(int(a));
}
long long pow(long long n, long long m, long long mod = 0) {
  if (m < 0) return 0;
  long long ans = 1;
  long long k = n;
  while (m) {
    if (m & 1) {
      ans *= k;
      if (mod) ans %= mod;
    }
    k *= k;
    if (mod) k %= mod;
    m >>= 1;
  }
  return ans;
}
template <class t1, class t2>
inline void add(t1 &a, t2 b, int mod = -1) {
  if (mod == -1) mod = 1000000007;
  a += b;
  while (a >= mod) a -= mod;
  while (a < 0) a += mod;
}
template <class t>
void output1(t arr) {
  for (int i = 0; i < (int)arr.size(); i++) cerr << arr[i] << ' ';
  cerr << endl;
}
template <class t>
void output2(t arr) {
  for (int i = 0; i < (int)arr.size(); i++) output1(arr[i]);
}
const int maxn = 600100;
int p[maxn * 2], lp, rp[maxn * 2], lrp;
int h[maxn], tono[maxn];
int n, m, c;
int dp[maxn], biao[maxn];
bool cant[maxn];
pair<pair<int, int>, int> orig[maxn], rorig[maxn];
vector<int> st[maxn], rst[maxn], ren[maxn];
int tdp[maxn];
vector<int> contain[maxn];
int maxOver[maxn];
int main() {
  ios_base::sync_with_stdio(0);
  scanf("%d%d", &n, &c);
  lp = 1;
  for (int i = 0; i < n; i++) {
    scanf("%d%d%d", &orig[i].first.first, &orig[i].first.second,
          &orig[i].second);
    p[lp++] = orig[i].first.first;
    p[lp++] = orig[i].first.second;
  }
  sort(orig, orig + n);
  sort(p, p + lp);
  lp = unique(p, p + lp) - p;
  for (int i = 0; i < n; i++) {
    orig[i].first.first = find(orig[i].first.first, p, lp);
    orig[i].first.second = find(orig[i].first.second, p, lp);
    st[orig[i].first.first].push_back(i);
    h[orig[i].first.first]++;
    h[orig[i].first.second]--;
  }
  lrp = 1;
  for (int i = 1; i < lp; i++) {
    h[i] += h[i - 1];
    if (h[i] <= 2) {
      rp[lrp++] = p[i];
      tono[lrp - 1] = i;
    } else if (h[i - 1] <= 2) {
      rp[lrp++] = p[i];
      tono[lrp - 1] = i;
    }
  }
  for (int i = 0; i < n; i++) {
    rorig[i].first.first = find(p[orig[i].first.first], rp, lrp, 0);
    if (h[tono[rorig[i].first.first]] > 2) {
      rorig[i].first.first++;
    }
    rorig[i].first.second = find(p[orig[i].first.second], rp, lrp);
    if (h[tono[rorig[i].first.second] - 1] > 2) {
      rorig[i].first.second--;
    }
    rorig[i].second = orig[i].second;
    rst[rorig[i].first.first].push_back(i);
  }
  set<int> in;
  for (int i = 0; i < lrp; i++) {
    for (auto it : rst[i])
      if (rorig[it].first.second > rorig[it].first.first) {
        ren[rorig[it].first.second].push_back(it);
        in.insert(it);
      }
    for (auto it : ren[i]) in.erase(it);
    ren[i].clear();
    if (in.size() <= 2) {
      for (auto it : in) {
        contain[i].push_back(it);
      }
    }
  }
  int rc = c;
  pair<int, int> rhave = make_pair(-1, -1);
  int currentOver = 0;
  for (int i = 0; i < lrp; i++) {
    if (c < 0) cant[i] = 1;
    dp[i + 1] = dp[i];
    for (auto no : ren[i]) {
      if (no == rhave.first) {
        swap(rhave.first, rhave.second);
      }
      rhave.second = -1;
      dp[i + 1] = min(dp[i + 1], biao[no]);
      c += rorig[no].second;
      currentOver = 0;
    }
    if (h[tono[i]] <= 2 && h[tono[i]] > 0) {
      dp[i + 1] += rp[i + 1] - rp[i];
      for (auto no : rst[i])
        if (rorig[no].first.second > rorig[no].first.first) {
          c -= rorig[no].second;
          biao[no] = dp[i];
          ren[rorig[no].first.second].push_back(no);
          if (rhave.first == -1)
            rhave.first = no;
          else
            rhave.second = no;
          int rsum = 0;
          if (c >= 0) {
            for (int j = i + 1; j < rorig[no].first.second; j++) {
              if (h[tono[j]] <= 2 && rhave.second != -1) {
                int maxv = 0;
                for (auto it : contain[j]) maxv = max(maxv, it);
                if (maxv <= no) {
                  rsum += rp[j + 1] - rp[j];
                }
                tdp[j + 1] = max(tdp[j + 1], rsum + dp[i + 1]);
              }
            }
          }
        }
      if (rhave.second == -1) {
        if (c >= 0)
          tdp[i + 1] = max(tdp[i + 1], dp[i + 1] + maxOver[rhave.first]);
      } else {
        currentOver += rp[i + 1] - rp[i];
        if (c >= 0) {
          maxOver[rhave.first] = max(maxOver[rhave.first], currentOver);
          tdp[i + 1] =
              max(tdp[i + 1], dp[i + 1] - currentOver + maxOver[rhave.first]);
        }
      }
    }
    for (auto no : ren[i]) {
      if (rhave.first != -1) {
        biao[rhave.first] = min(biao[no], biao[rhave.first]);
      }
      if (rhave.second != -1) {
        biao[rhave.second] = min(biao[no], biao[rhave.second]);
      }
    }
    ren[i].clear();
  }
  for (int i = 1; i < lrp; i++) {
    if (cant[i]) {
      dp[i] = dp[i - 1];
    } else {
      dp[i] = max(dp[i], dp[i - 1]);
    }
    dp[i] = max(dp[i], tdp[i]);
  }
  int sumv = 0;
  for (int i = 0; i < lrp; i++) {
    dp[i] += sumv;
    if (h[tono[i]] == 0) sumv += rp[i + 1] - rp[i];
  }
  map<int, int> rtt;
  int lastno = -1, currentsum = 0, max1 = 0;
  int sum0 = 0, maxdp = 0;
  for (int i = 0; i < lrp; i++) {
    if (h[tono[i]] == 0) {
      sum0 += rp[i + 1] - rp[i];
      dp[i + 1] = max(dp[i + 1], maxdp + sum0);
      continue;
    }
    for (auto it : rst[i])
      if (rorig[it].first.second > rorig[it].first.first) {
        if (lastno == -1 ||
            rorig[it].first.second > rorig[lastno].first.second) {
          lastno = it;
          currentsum = 0;
          max1 = 0;
          auto rit = rtt.upper_bound(rc - rorig[it].second);
          if (rit != rtt.begin()) {
            rit--;
            max1 = rit->second;
          }
        }
      }
    if (h[tono[i]] == 1 && rorig[lastno].second <= rc) {
      currentsum += rp[i + 1] - rp[i];
      maxdp = max(currentsum + max1, maxdp);
      auto rit = rtt.lower_bound(rorig[lastno].second);
      bool flag = 1;
      if (rit != rtt.begin()) {
        auto rtit = rit;
        rtit--;
        if (rtit->second > currentsum) flag = 0;
      }
      while (flag && rit != rtt.end() && rit->second <= currentsum) {
        auto temp = rit;
        rit++;
        rtt.erase(temp);
      }
      if (flag) {
        rtt.insert(make_pair(rorig[lastno].second, currentsum));
      }
    }
    dp[i + 1] = max(dp[i + 1], maxdp + sum0);
  }
  scanf("%d", &m);
  for (int i = 0; i < m; i++) {
    int val;
    scanf("%d", &val);
    if (val > dp[lrp - 1])
      printf("%d\n", rp[lrp - 1] + val - dp[lrp - 1]);
    else {
      int trp = find(val, dp, lrp, 0, 1);
      printf("%d\n", rp[trp] + val - dp[trp]);
    }
  }
  return 0;
}