namespace cust {
#define let auto
#define match switch
#define fn auto
#define type using
#define mod namespace
#define self this
#define static_ static auto

using i32 = std::int32_t;
using i64 = std::int64_t;
using u32 = std::uint32_t;
using u64 = std::uint64_t;
using usize = std::size_t;
using str = string_view;
template <typename T> using Vec = std::vector<T>;

#define assert_eq(a, b)                                                        \
  do {                                                                         \
    if (a != b) {                                                              \
      panic("left:{}\nright:{}", a, b);                                        \
    }                                                                          \
  } while (0)

#define assert_ne(a, b)                                                        \
  do {                                                                         \
    if (a == b) {                                                              \
      panic("left:{}\nright:{}", a, b)                                         \
    }                                                                          \
  } while (0)

#ifdef __cpp_lib_format
template <typename... _Args>
inline void println(format_string<_Args...> __fmt, _Args &&...__args) {
  let output = std::format(__fmt, std::forward<_Args>(__args)...);
  printf("%s\n", output.c_str());
}

template <typename... _Args>
inline void eprintln(format_string<_Args...> __fmt, _Args &&...__args) {
  let output = std::format(__fmt, std::forward<_Args>(__args)...);
  fprintf(stderr, "%s\n", output.c_str());
}

template <typename... _Args>
inline void print(format_string<_Args...> __fmt, _Args &&...__args) {
  let output = std::format(__fmt, std::forward<_Args>(__args)...);
  printf("%s", output.c_str());
}

template <typename... _Args>
inline void eprint(format_string<_Args...> __fmt, _Args &&...__args) {
  let output = std::format(__fmt, std::forward<_Args>(__args)...);
  fprintf(stderr, "%s", output.c_str());
}
#else
#error unsupported
#endif

template <typename... _Args>
[[noreturn]]
fn panic_internal(format_string<_Args...> __fmt, _Args &&...__args) {
  let output = std::format(__fmt, std::forward<_Args>(__args)...);
  eprintln("{}", output);
  exit(233);
}

template <typename T> fn get_str(const T &t) -> string {
  stringstream s;
  s << t;
  string out;
  s >> out;
  return out;
}

#define panic(...)                                                             \
  do {                                                                         \
    eprintln("Thread \'{}\' panicked at {}:{}:",                               \
             get_str(this_thread::get_id()), __FILE__, __LINE__);              \
    panic_internal(__VA_ARGS__);                                               \
  } while (0)

#define dbg(val) eprintln("line {}:{}={}", __LINE__, #val, val)

template <typename T> class Option {
public:
  static fn Some(T data) -> Option { return Option<T>(std::optional<T>(data)); }

  static fn None() -> Option { return Option<T>(std::nullopt); }

  fn unwrap() -> T {
    if (self->internal.has_value()) {
      return self->internal.value();
    } else {
      panic("Option is None.");
    }
  }

  fn operator==(const Option<T> &cmp) const->bool {
    return self->internal == cmp.internal;
  }

private:
  std::optional<T> internal;

  Option(std::optional<T> data) : internal(data) {}
};

template <typename T> class VecDeque {
public:
  static fn new_() { return VecDeque(); }

  fn push_back(const T &data) { self->internal_collection.push_back(data); }

  fn push_front(const T &data) { self->internal_collection.push_front(data); }

  fn pop_back() -> Option<T> {
    if (self->is_empty()) {
      return Option<T>::None();
    } else {
      let ret = self->back();
      self->internal_collection.pop_back();
      return ret;
    }
  }

  fn pop_front() -> Option<T> {
    if (self->is_empty()) {
      return Option<T>::None();
    } else {
      let ret = self->back();
      self->internal_collection.pop_front();
      return ret;
    }
  }

  fn is_empty() const -> bool { return self->internal_collection.empty(); }

  fn len() const -> usize { return self->internal_collection.size(); }

  fn front() const -> Option<T> {
    if (!self->is_empty()) {
      return Option<T>::Some(self->internal_collection.front());
    } else {
      return Option<T>::None();
    }
  }

  fn back() const -> Option<T> {
    if (!self->is_empty()) {
      return Option<T>::Some(self->internal_collection.back());
    } else {
      return Option<T>::None();
    }
  }

  fn operator[](usize pos)->T & {
    if (pos >= self->len()) {
      panic("out of range");
    }
    return self->internal_collection[pos];
  }

private:
  std::deque<T> internal_collection;

  VecDeque() {}
};

class String {
public:
  static fn new_() -> String { return String(); }

  static fn from(str source) -> String { return String(source); }

  friend fn operator>>(istream &in, String &s)->istream & {
    in >> s.internal;
    return in;
  }

  /// extension, not in rust std
  fn ascii_index(usize idx) -> char {
    if (idx >= self->len()) {
      panic("index out of bound: the len is {} but the index is {}",
            self->len(), idx);
    }
    return self->internal[idx];
  }

  fn len() -> usize { return self->internal.length(); }

  std::string internal;

private:
  String(str source) : internal(source) {}

  String() {}
};
}