#include #define overload4(_1, _2, _3, _4, name, ...) name #define rep1(i, n) for (ll i = 0; i < ll(n); ++i) #define rep2(i, s, n) for (ll i = ll(s); i < ll(n); ++i) #define rep3(i, s, n, d) for(ll i = ll(s); i < ll(n); i+=d) #define rep(...) overload4(__VA_ARGS__,rep3,rep2,rep1)(__VA_ARGS__) #define rrep1(i, n) for (ll i = ll(n)-1; i >= 0; i--) #define rrep2(i, n, t) for (ll i = ll(n)-1; i >= (ll)t; i--) #define rrep3(i, n, t, d) for (ll i = ll(n)-1; i >= (ll)t; i-=d) #define rrep(...) overload4(__VA_ARGS__,rrep3,rrep2,rrep1)(__VA_ARGS__) #define all(a) a.begin(),a.end() #define rall(a) a.rbegin(),a.rend() #define SUM(a) accumulate(all(a),0LL) #define MIN(a) *min_element(all(a)) #define MAX(a) *max_element(all(a)) #define popcount(x) __builtin_popcountll(x) #define pb push_back #define eb emplace_back #ifdef __LOCAL #define debug(...) { cout << #__VA_ARGS__; cout << ": "; print(__VA_ARGS__); cout << flush; } #else #define debug(...) void(0) #endif #define INT(...) int __VA_ARGS__;scan(__VA_ARGS__) #define LL(...) ll __VA_ARGS__;scan(__VA_ARGS__) #define STR(...) string __VA_ARGS__;scan(__VA_ARGS__) #define CHR(...) char __VA_ARGS__;scan(__VA_ARGS__) #define DBL(...) double __VA_ARGS__;scan(__VA_ARGS__) #define LD(...) ld __VA_ARGS__;scan(__VA_ARGS__) using namespace std; using ll = long long; using ld = long double; using P = pair; using LP = pair; using vi = vector; using vvi = vector; using vl = vector; using vvl = vector; using vd = vector; using vvd = vector; using vs = vector; using vc = vector; using vvc = vector; using vb = vector; using vvb = vector; using vp = vector

; using vvp = vector; template istream &operator>>(istream &is, pair &p) { return is >> p.first >> p.second; } template ostream &operator<<(ostream &os, const pair &p) { return os << '{' << p.first << ", " << p.second << '}'; } template istream &operator>>(istream &is, tuple &t) { return is >> get<0>(t) >> get<1>(t) >> get<2>(t); } template ostream &operator<<(ostream &os, const tuple &t) { return os << '{' << get<0>(t) << ", " << get<1>(t) << ", " << get<2>(t) << '}'; } template istream &operator>>(istream &is, vector &v) { for (T &t:v) { is >> t; } return is; } template ostream &operator<<(ostream &os, const vector &v) { os << '['; rep(i, v.size())os << v[i] << (i == int(v.size() - 1) ? "" : ", "); return os << ']'; } template void vecout(const vector &v, char div = '\n') { rep(i, v.size()) cout << v[i] << (i == int(v.size() - 1) ? '\n' : div); } template bool chmin(T &a, T b) { if (a > b) { a = b; return true; } return false; } template bool chmax(T &a, T b) { if (a < b) { a = b; return true; } return false; } void scan() {} template void scan(Head &head, Tail &... tail) { cin >> head; scan(tail...); } template void print(const T &t) { cout << t << '\n'; } template void print(const Head &head, const Tail &... tail) { cout << head << ' '; print(tail...); } template void fin(const T &... a) { print(a...); exit(0); } struct Init_io { Init_io() { ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); cout << boolalpha << fixed << setprecision(15); cerr << boolalpha << fixed << setprecision(15); } } init_io; const string yes[] = {"no", "yes"}; const string Yes[] = {"No", "Yes"}; const string YES[] = {"NO", "YES"}; const int inf = 1001001001; const ll linf = 1001001001001001001; template vector cumsum(const vector &v, bool shift_one = true) { int n = v.size(); vector res; if (shift_one) { res.resize(n + 1); rep(i, n) res[i + 1] = res[i] + v[i]; } else { res.resize(n); if (n) { res[0] = v[0]; rep(i, 1, n) res[i] = res[i - 1] + v[i]; } } return res; } vvi graph(int n, int m, bool directed = false, int origin = 1) { vvi G(n); rep(_, m) { INT(u, v); u -= origin, v -= origin; G[u].pb(v); if (!directed) G[v].pb(u); } return G; } template vector>> weighted_graph(int n, int m, bool directed = false, int origin = 1) { vector>> G(n); rep(_, m) { int u, v; T w; scan(u, v, w); u -= origin, v -= origin; G[u].eb(v, w); if (!directed) G[v].eb(u, w); } return G; } template class matrix : public vector> { public: using vector>::vector; constexpr int get_h() const { return this->size(); } constexpr int get_w() const { return (get_h() ? (*this)[0].size() : 0); } constexpr matrix &operator+=(const matrix &a) { rep(i, get_h()) rep(j, get_w()) (*this)[i][j] += a[i][j]; return *this; } constexpr matrix &operator*=(const int &k) { rep(i, get_h()) rep(j, get_w()) (*this)[i][j] *= k; return *this; } constexpr matrix &operator-=(const matrix &a) { *this += a * (-1); return *this; } constexpr matrix operator+(const matrix &a) const { return res(*this) += a; } constexpr matrix operator*(const int &k) const { return res(*this) *= k; } constexpr matrix operator-(const matrix &a) const { return res(*this) -= a; } constexpr matrix operator*(const matrix &a) const { int h = get_h(), w = get_w(), ah = a.get_h(), aw = a.get_w(); assert(w == ah); matrix res(h, vector(aw)); rep(i, h) rep(j, w) rep(k, aw) res[i][k] += (*this)[i][j] * a[j][k]; return res; } constexpr matrix &operator*=(const matrix &a) { return *this = *this * a; } constexpr matrix pow(ll t) const { int h = get_h(), w = get_w(); assert(h == w); matrix res(h, vector(w)), a(*this); rep(i, get_h()) res[i][i] = 1; while (t > 0) { if (t & 1) res *= a; t >>= 1; a *= a; } return res; } }; using mat = matrix; const double eps = 1e-9; // return the rank of the matrix // O(h * w^2) template int GaussJordan(matrix &a, bool isExtended) { int rank = 0; rep(col, a.get_w()) { if (isExtended and col == a.w - 1) break; int pivot = -1; rep(row, rank, a.get_h()) { if (a[row][col] != 0) pivot = row; } if (pivot == -1) continue; swap(a[pivot], a[rank]); // fix the value of pivot 1 rrep(col2, a.get_w()) a[rank][col2] /= a[rank][col]; rep(row, a.get_h()) { if (row == rank) continue; if (a[row][col] == 0) continue; T fac = a[row][col]; rep(col2, a.get_w()) a[row][col2] -= a[rank][col2] * fac; } rank++; } return rank; } template<> int GaussJordan(matrix &a, bool isExtended) { int rank = 0; rep(col, a.get_w()) { if (isExtended and col == a.get_w() - 1) break; int pivot = -1; double mx = eps; rep(row, rank, a.get_h()) { if (abs(a[row][col]) > mx) { mx = abs(a[row][col]); pivot = row; } } if (pivot == -1) continue; swap(a[pivot], a[rank]); // fix the value of pivot 1 rrep(col2, a.get_w()) a[rank][col2] /= a[rank][col]; rep(row, a.get_h()) { if (row == rank) continue; if (abs(a[row][col]) <= eps) continue; double fac = a[row][col]; rep(col2, a.get_w()) a[row][col2] -= a[rank][col2] * fac; } rank++; } return rank; } // solve ax = b reference: https://drken1215.hatenablog.com/entry/2019/03/20/202800 // if there is no solution, return empty vector // otherwise, return one solution (all parameters is fixed 0) // if T is mint, calculate the numbers of solutions by 'mod^(n-rank)' // if T is mint, mod must be a prime template vector linear_equation(matrix &a, vector &b) { assert(a.get_h() == (int) b.size()); matrix m(a.get_h(), a.get_w() + 1); rep(i, a.get_h()) { rep(j, a.get_w()) m[i][j] = a[i][j]; m[i][a.get_w()] = b[i]; } int rank = GaussJordan(m, true); vector res; rep(row, rank, a.get_h()) { if (m[row][a.get_w()] != 0) return res; } res.assign(a.get_w(), 0); rep(i, rank) { rep(j, a.get_w()) { if (m[i][j] != 0) { res[j] = m[i][a.get_w()]; break; } } } return res; } template<> vd linear_equation(matrix &a, vector &b) { assert(a.get_h() == (int) b.size()); matrix m(a.get_h(), vd(a.get_w() + 1)); rep(i, a.get_h()) { rep(j, a.get_w()) m[i][j] = a[i][j]; m[i][a.get_w()] = b[i]; } int rank = GaussJordan(m, true); vd res; rep(row, rank, a.get_h()) { if (abs(m[row][a.get_w()]) > eps) return res; } res.assign(a.get_w(), 0); rep(i, rank) { rep(j, a.get_w()) { if (abs(m[i][j]) > eps) { res[j] = m[i][a.get_w()]; break; } } } return res; } int main() { INT(n, l); vi d(n); vi b(2 * n); scan(d, b); vi x(2 * n); rep(i, n) x[i] = d[i]; rep(i, n) x[n + i] = l + d[i]; mat mt(2 * n, vd(2 * n)); vd v(2 * n); rep(i, 2 * n) { rep(j, 2 * n) { mt[j][i] = min(abs(x[i] - x[j]), 2 * l - abs(x[i] - x[j])); } v[i] = b[i]; } vd res = linear_equation(mt, v); print(res.empty() ? "No" : "Yes"); }