// #define MULTI_TESTCASE // #define AOJ_TESTCASE // #define FAST_CIO // #define INTERACTIVE #define EPS 1e-11 // https://github.com/miscalculation53/library/tree/wip/template/template_all.hpp // https://github.com/miscalculation53/library/tree/wip/template/template_all_but_modint.hpp // https://github.com/miscalculation53/library/tree/wip/template/template_types.hpp #include namespace { using namespace std; using ll = long long; using uint = unsigned int; using ull = unsigned long long; using pll = pair; #define vc vector template using vvc = vc>; using vl = vc; using vstr = vc; using i128 = __int128_t; using u128 = __uint128_t; i128 stoi128(const string &s) { const bool neg = s.front() == '-'; u128 res = 0; for (int i = neg; i < (int)s.size(); i++) res = 10 * res + s[i] - '0'; if (neg) return -i128(res - 1) - 1; return i128(res); } string i128tos(i128 x) { if (x == 0) return "0"; string sign = "", res = ""; u128 ux; if (x < 0) ux = u128(-(x + 1)) + 1, sign = "-"; else ux = x; while (ux > 0) { res += '0' + ux % 10; ux /= 10; } reverse(res.begin(), res.end()); return sign + res; } #define cauto const auto // https://github.com/miscalculation53/library/tree/wip/template/template_rep.hpp #define overload4(_1,_2,_3,_4,name,...) name #define rep1(i,n) for (ll i = 0, nnnnn = ll(n); i < nnnnn; i++) #define rep(...) overload4(__VA_ARGS__, rep3, rep2, rep1)(__VA_ARGS__) #define repi1(i,n) for (int i = 0, nnnnn = int(n); i < nnnnn; i++) #define repi(...) overload4(__VA_ARGS__, repi3, repi2, repi1)(__VA_ARGS__) #define fe(...) for (auto __VA_ARGS__) // https://github.com/miscalculation53/library/tree/wip/template/template_math.hpp // https://github.com/miscalculation53/library/tree/wip/utils/is_integral_ext.hpp template constexpr bool is_integral_ext = is_integral_v || is_same_v || is_same_v; template constexpr bool is_signed_ext = is_signed_v || is_same_v; template constexpr bool is_unsigned_ext = is_unsigned_v || is_same_v; // https://github.com/miscalculation53/library/tree/wip/utils/default_infty.hpp namespace default_infty_detail { template inline constexpr bool unsupported = false; } template inline bool chmax(T &a, U b) { return a < b ? a = b, true : false; } template && is_integral_ext>> inline constexpr T divfloor(U a, V b) { return T(a) / T(b) - (T(a) % T(b) && (T(a) ^ T(b)) < 0); } template && is_integral_ext>> inline constexpr T safemod(U a, V b) { return T(a) - T(b) * divfloor(a, b); } // https://github.com/miscalculation53/library/tree/wip/template/template_vector.hpp #define ALL(a) (a).begin(), (a).end() template inline T SZ(const V &x) { return x.size(); } // https://github.com/miscalculation53/library/tree/wip/template/template_algo.hpp // https://github.com/miscalculation53/library/tree/wip/utils/resolved_infty.hpp // https://github.com/miscalculation53/library/tree/wip/utils/resolved_value.hpp template struct has_e0 : false_type {}; template struct has_e0> : true_type {}; template inline constexpr bool has_e0_v = has_e0::value; namespace internal { } constexpr array DRULgrid = {{{1, 0}, {0, 1}, {-1, 0}, {0, -1}}}; constexpr array DRULplane = {{{0, -1}, {1, 0}, {0, 1}, {-1, 0}}}; // https://github.com/miscalculation53/library/tree/wip/template/template_binsearch.hpp template struct is_random_access_iterator { static constexpr bool value = is_same_v< typename iterator_traits::iterator_category, random_access_iterator_tag >; }; template constexpr bool is_random_access_iterator_v = is_random_access_iterator::value; namespace internal { }; // https://github.com/miscalculation53/library/tree/wip/template/template_bit.hpp template inline constexpr ull MASK(T k) { return (1ULL << k) - 1ULL; } inline constexpr ll bit_width(ll x) { return std::bit_width((ull)x); } inline constexpr ll bit_floor(ll x) { return std::bit_floor((ull)x); } inline constexpr ll bit_ceil(ll x) { return std::bit_ceil((ull)x); } inline constexpr ll countr_zero(ll x) { assert(x != 0); return std::countr_zero((ull)x); } inline constexpr ll popcount(ll x) { return std::popcount((ull)x); } inline constexpr bool has_single_bit(ll x) { return std::has_single_bit((ull)x); } // https://github.com/miscalculation53/library/tree/wip/template/template_inout.hpp // https://github.com/miscalculation53/library/tree/wip/template/template_dump.hpp // https://github.com/miscalculation53/library/tree/wip/template/template_dump_map.hpp #define dump(...) #define oj(...) __VA_ARGS__ namespace fastio { template struct unsigned_integer { using type = make_unsigned_t; }; template <> struct unsigned_integer { using type = u128; }; template <> struct unsigned_integer { using type = u128; }; template using unsigned_integer_t = typename unsigned_integer::type; static constexpr uint32_t SIZ = 1 << 17; char ibuf[SIZ]; char obuf[SIZ]; char out[100]; uint32_t pil = 0, pir = 0, por = 0; struct Pre { char num[10000][4]; constexpr Pre() : num() { for (int i = 0; i < 10000; i++) { int n = i; for (int j = 3; j >= 0; j--) { num[i][j] = n % 10 | '0'; n /= 10; } } } } constexpr pre; inline void load() { memcpy(ibuf, ibuf + pil, pir - pil); pir = pir - pil + fread(ibuf + pir - pil, 1, SIZ - pir + pil, stdin); pil = 0; if (pir < SIZ) ibuf[pir++] = '\n'; } inline void flush() { fwrite(obuf, 1, por, stdout); por = 0; } void rd1(string &x) { x.clear(); while (true) { if (pil == pir) load(); while (pil < pir && ibuf[pil] <= ' ') ++pil; if (pil < pir) break; } while (true) { uint32_t p = pil; while (pil < pir && ibuf[pil] > ' ') ++pil; x.append(ibuf + p, pil - p); if (pil < pir) { ++pil; return; } load(); } } template void rd1_real(T &x) { string s; rd1(s); if constexpr (!is_same_v) { auto [p, ec] = from_chars(s.data(), s.data() + s.size(), x); if (ec == errc{} && p == s.data() + s.size()) return; } if constexpr (is_same_v) x = stold(s); else x = stod(s); } template void rd1_integer(T &x) { using U = unsigned_integer_t; bool minus = false; U val = 0; if constexpr (check_buffer) if (pil + 100 > pir) load(); uint32_t p = pil; while (ibuf[p] < '-') ++p; if constexpr (is_signed::value || is_same_v) { if (ibuf[p] == '-') minus = true, ++p; } while ('0' <= ibuf[p]) val = val * 10 + (ibuf[p++] & 15); pil = p; if constexpr (is_signed::value || is_same_v) { if (minus) { const U min_abs = U(numeric_limits::max()) + 1; x = val == min_abs ? numeric_limits::lowest() : -T(val); } else x = T(val); } else x = T(val); } void rd1(ll &x) { rd1_integer(x); } template void rd1(vc &x) { for (auto &d: x) rd1(d); } template void read(T &...x) { if constexpr (sizeof...(T) <= SIZ / 100 && ((!is_same_v && (is_integral_v || is_same_v || is_same_v)) && ...)) { if (pil + 100 * sizeof...(T) > pir) load(); (rd1_integer(x), ...); } else (rd1(x), ...); } void wt1(const char c) { if (por == SIZ) flush(); obuf[por++] = c; } void wt1(string_view s) { while (!s.empty()) { if (por == SIZ) flush(); size_t n = min(s.size(), SIZ - por); memcpy(obuf + por, s.data(), n); por += n; s.remove_prefix(n); } } template void wt1_integer(T x) { if (por > SIZ - 100) flush(); using U = unsigned_integer_t; U ux; if constexpr (is_signed::value || is_same_v) { if (x < 0) obuf[por++] = '-', ux = U(0) - U(x); else ux = U(x); } else ux = x; int outi; for (outi = 96; ux >= 10000; outi -= 4) { memcpy(out + outi, pre.num[ux % 10000], 4); ux /= 10000; } if (ux >= 1000) { memcpy(obuf + por, pre.num[ux], 4); por += 4; } else if (ux >= 100) { memcpy(obuf + por, pre.num[ux] + 1, 3); por += 3; } else if (ux >= 10) { int q = (ux * 103) >> 10; obuf[por] = q | '0'; obuf[por + 1] = (ux - q * 10) | '0'; por += 2; } else obuf[por++] = ux | '0'; memcpy(obuf + por, out + outi + 4, 96 - outi); por += 96 - outi; } template void wt1_real(T x) { if constexpr (!is_same_v) { auto [p, ec] = to_chars(out, out + sizeof(out), x, chars_format::fixed, 15); if (ec == errc{}) { wt1(string_view(out, p)); return; } } ostringstream oss; oss << fixed << setprecision(15) << x; wt1(oss.str()); } template , int> = 0> void wt1(T x); template void wt1(const pair &val); template void wt1(const tuple &tpl); template void wt1(const array &val); template void wt1(const vector &val); template void write(T &&...x) { (wt1(std::forward(x)), ...); } template void print(T &&...x) { if constexpr (sizeof...(T)) { int i = 0; ((i++ ? wt1(' ') : void(), wt1(std::forward(x))), ...); } wt1('\n'); } } struct Dummy { Dummy() { atexit(fastio::flush); } } dummy; namespace internal { template void READnodump(Ts &...a) { fastio::read(a...); } template void READVECnodump(int n, vc &...v) { (v.resize(n), ...); READnodump(v...); } }; #define READ(...) internal::READnodump(__VA_ARGS__); dump(__VA_ARGS__) #define IN(T,...) T __VA_ARGS__; READ(__VA_ARGS__) #define LL(...) IN(ll, __VA_ARGS__) #define READVEC(...) internal::READVECnodump(__VA_ARGS__); dump(__VA_ARGS__) #define VEC(T,n,...) vc __VA_ARGS__; READVEC(n, __VA_ARGS__) #define PRINT fastio::print namespace internal { }; namespace internal { }; // https://github.com/miscalculation53/library/tree/wip/template/template_random.hpp mt19937_64 mt; namespace internal { }; // https://github.com/miscalculation53/library/tree/wip/math/modint/template_modint.hpp // https://github.com/miscalculation53/library/tree/wip/math/modint/modint.hpp // https://github.com/miscalculation53/library/tree/wip/math/modint/modint_internal_static.hpp // https://github.com/miscalculation53/library/tree/wip/utils/larger_int.hpp namespace larger_int_detail { } template struct larger_int { private: static constexpr bool check(); static_assert(check()); public: using type = T; }; #define LARGER_INT(T,U) template <> struct larger_int { using type = U; }; LARGER_INT(signed char, short) LARGER_INT(short, int) LARGER_INT(int, long long) LARGER_INT(long, __int128_t) LARGER_INT(long long, __int128_t) LARGER_INT(unsigned char, unsigned short) LARGER_INT(unsigned short, unsigned int) LARGER_INT(unsigned int, unsigned long long) LARGER_INT(unsigned long, __uint128_t) LARGER_INT(unsigned long long, __uint128_t) #undef LARGER_INT template struct Rational; template struct larger_int> { using type = Rational::type>; }; template using larger_int_t = typename larger_int::type; // https://github.com/miscalculation53/library/tree/wip/math/modint/modint_internal_isprime.hpp namespace internal { template constexpr ll powmod_constexpr(ll x, ll n, T m) { if (m == 1) return 0; using U = make_unsigned_t; using L = larger_int_t; U r = 1, y = safemod(x, m); while (n) { if (n & 1) r = L(r) * y % m; y = L(y) * y % m; n >>= 1; } return r; } template constexpr bool isprime = isprime_constexpr(n); }; namespace internal { template struct policy_static { using mod_type = decltype(M); using value_type = make_unsigned_t; using calc_type = larger_int_t; static constexpr bool is_prime = isprime_constexpr(M); static constexpr value_type init(value_type v) { return v; } static constexpr mod_type val(value_type v); }; }; // https://github.com/miscalculation53/library/tree/wip/math/modint/modint_internal_barrett32.hpp namespace internal { struct barrett32 { uint m; ull im; explicit barrett32(uint m) : m(m), im((ull)(-1) / m + 1) {} }; template struct policy_barrett32 { using value_type = uint; using calc_type = ull; using mod_type = int; static constexpr bool is_prime = false; static inline barrett32 reducer{998244353}; static value_type init(value_type v) { return v; } static mod_type val(value_type v); }; }; // https://github.com/miscalculation53/library/tree/wip/math/modint/modint_internal_montgomery64.hpp namespace internal { inline constexpr ull inv64(ull a) { ull x = a; while (a * x != 1) x *= 2 - a * x; return x; } struct montgomery64odd { ull m, im, sq; explicit montgomery64odd(ull m) : m(m), im(inv64(m)), sq(-u128(m) % m) {} ull umod() const { return m; } ull reduce(u128 x) const { auto t = (x + u128(m) * (-im * ull(x))) >> 64; if (t >= m) t -= m; return (ull)t; } ull inv_reduce(i128 v) const { return reduce(u128(v % m + m) * sq); } }; struct montgomery64 { ull m, mx, imx, d, q; uint b; explicit montgomery64(ull m) : m(m) { b = countr_zero(m), mx = m >> b; imx = inv64(mx); d = powmod_constexpr((mx + 1) / 2, b, mx); u128 sq = -u128(mx) % mx; q = (1 + (((sq - 1) * d) << b)) % m; } ull umod() const { return m; } ull reduce(u128 x) const { if (b == 0) { auto t = (x + u128(mx) * (-imx * ull(x))) >> 64; if (t >= m) t -= m; return (ull)t; } ull p = x & MASK(b); x = (x >> b) + p * d; ull y = p << (64 - b); auto t = (x + u128(mx) * (imx * (y - ull(x)))) >> (64 - b); if (t >= m) { t -= m; if (t >= m) t -= m; } return (ull)t; } ull inv_reduce(i128 v) const { return reduce(u128(v % m + m) * q); } }; template struct policy_montgomery64_odd { using value_type = ull; using calc_type = u128; using mod_type = ll; static constexpr bool is_prime = false; static inline montgomery64odd reducer{(1LL << 61) - 1}; static value_type init(value_type v) { return reducer.inv_reduce(v); } static mod_type val(value_type v); }; template struct policy_montgomery64 { using value_type = ull; using calc_type = u128; using mod_type = ll; static constexpr bool is_prime = false; static inline montgomery64 reducer{(1LL << 61) - 1}; static value_type init(value_type v) { return reducer.inv_reduce(v); } static mod_type val(value_type v); }; }; // https://github.com/miscalculation53/library/tree/wip/math/extgcd.hpp namespace internal { template struct modint_impl { using V = typename Policy::value_type; using M = typename Policy::mod_type; using mint = modint_impl; private: V _v; public: modint_impl(); template >> modint_impl(T v); M val() const; friend mint operator+(const mint &lhs, const mint &rhs) { return mint(lhs) += rhs; } friend mint operator-(const mint &lhs, const mint &rhs) { return mint(lhs) -= rhs; } friend mint operator*(const mint &lhs, const mint &rhs) { return mint(lhs) *= rhs; } friend mint operator/(const mint &lhs, const mint &rhs) { return mint(lhs) /= rhs; } friend bool operator==(const mint &lhs, const mint &rhs) { return lhs._v == rhs._v; } friend bool operator!=(const mint &lhs, const mint &rhs) { return lhs._v != rhs._v; } friend void rd1(mint &x) { long long a; fastio::rd1(a); x = a; } friend void wt1(const mint &x) { fastio::wt1(x.val()); } }; }; template using static_modint32 = internal::modint_impl>; template using dynamic_modint32 = internal::modint_impl>; template using static_modint64 = internal::modint_impl>; template using dynamic_modint64_odd = internal::modint_impl>; template using dynamic_modint64 = internal::modint_impl>; using modint998244353 = static_modint32<998244353>; template struct is_modint : std::false_type { }; template struct is_modint> : std::true_type { }; template inline constexpr bool is_modint_v = is_modint::value; template struct is_static_modint : false_type {}; template struct is_static_modint> : true_type {}; template struct is_static_modint> : true_type {}; template inline constexpr bool is_static_modint_v = is_static_modint::value; template struct is_dynamic_modint : false_type {}; template struct is_dynamic_modint> : true_type {}; template struct is_dynamic_modint> : true_type {}; template struct is_dynamic_modint> : true_type {}; template inline constexpr bool is_dynamic_modint_v = is_dynamic_modint::value; // https://github.com/miscalculation53/library/tree/wip/math/modint/power_table.hpp // https://github.com/miscalculation53/library/tree/wip/math/modint/binomial.hpp template struct Binomial { private: inline static decltype(T::mod()) mod; public: inline static vc fac_, finv_, inv_; }; // https://github.com/miscalculation53/library/tree/wip/math/modint/stom.hpp // https://github.com/miscalculation53/library/tree/wip/math/modint/to_rational.hpp // https://github.com/miscalculation53/library/tree/wip/math/svp2d.hpp namespace cpp_dump { template struct rat_value { T p, q; friend ostream &operator<<(ostream &os, const rat_value &x) { os << x.p; if (x.q != 1) os << '/' << x.q; return os; } }; template inline constexpr bool rat_is_map = false; template inline constexpr bool rat_is_map> = true; template inline constexpr bool rat_is_map> = true; template inline constexpr bool rat_is_map> = true; template inline constexpr bool rat_is_map> = true; struct rat_closure : std::ranges::range_adaptor_closure { }; } using mint = modint998244353; // using mint = modint1000000007; // using mint = static_modint<1000000000>; // using mint = modint; void init() { oj(mt.seed(random_device()())); } void main2() { LL(N, K); LL(M1); VEC(ll, M1, A); LL(M2); VEC(ll, M2, B); string S(N + 1, '.'); fe(a : A) S[a] = 'A'; fe(b : B) S[b] = 'B'; // 0: 行けない、1: 汚れて行ける、2: 汚れず行ける // maximize vl dp(N + 1, 0); dp[0] = 2; rep(i, N) { if (S[i] == 'A' && dp[i]) dp[i] = 1; if (S[i] == 'B' && dp[i]) dp[i] = 2; chmax(dp[i + 1], dp[i]); if (i + K <= N) chmax(dp[i + K], dp[i]); } PRINT(dp[N] == 2 ? "Yes" : "No"); dump(dp | cp::index()); } void test() { } // https://github.com/miscalculation53/library/tree/wip/template/template_main.hpp template struct Main { Main() { cauto CERR = [](string val, string color) { string s = "\033[" + color + "m" + val + "\033[m"; }; CERR("\n[FAST_IO]\n\n", "32"); cout << fixed << setprecision(20); init(); CERR("\n[SINGLE_TESTCASE]\n\n", "36"); main2(); } }; Main main_dummy; } int main() {}