/**
 * code generated by JHelperX
 * More info: https://github.com/GoBigorGoHome/JHelperX
 * @author zjs
 */

#if not defined LOCAL and not defined NDEBUG
#define NDEBUG
#endif
#define debug(...)
#define show(...)
extern const bool show_all_failed_tests = false;
extern const bool compare_real_numbers = false;
// #define INTERACTIVE_MODE //对于交互题，取消此行注释。
//
// Created by zjsdu on 5/28/2020.
//

#ifndef JHELPER_EXAMPLE_PROJECT_LIBRARY_ALIAS_HPP_
#define JHELPER_EXAMPLE_PROJECT_LIBRARY_ALIAS_HPP_
#include <string>
#include <cassert>
#include <queue>
#ifndef JHELPER_EXAMPLE_PROJECT_LIBRARY_IO_HPP_
#define JHELPER_EXAMPLE_PROJECT_LIBRARY_IO_HPP_
#include <iostream>
#include <vector>
#include <tuple>
//
// Created by zjsdu on 10/22/2020.
//

#ifndef JHELPER_EXAMPLE_PROJECT_TASKS_TYPE_TRAITS_HPP_
#define JHELPER_EXAMPLE_PROJECT_TASKS_TYPE_TRAITS_HPP_
#include <type_traits>


#if __cplusplus >= 201703L
template<typename T> T type();// no definition
template<typename Container> auto value_type_of_() {
  if constexpr (std::is_array_v<Container>)
    return type<std::remove_extent_t<Container>>();
  else
    return type<typename Container::value_type>();
}
template<typename Container>
using value_type_of =
    decltype(value_type_of_<std::remove_reference_t<Container>>());
#else
template <typename Container>
struct value_type_of_impl // default, non-array
{
  using type = typename Container::value_type;
};

template <typename T, std::size_t N>
struct value_type_of_impl<T[N]> // arrays
{
  using type = T;
};

template <typename Container>
using value_type_of = typename value_type_of_impl<Container>::type;
#endif
// Source: https://foonathan.net/2020/10/iife-metaprogramming/

#if __cplusplus >= 201703L
namespace is_iterable_impl {
using std::begin;
using std::end;
template<typename T>
using check_specs = std::void_t<
    std::enable_if_t<
        std::is_same<decltype(begin(std::declval<T &>())),// has begin()
                       decltype(end(std::declval<T &>()))   // has end()
                       >::value>,// ... begin() and end() are the same type ...
    decltype(*begin(std::declval<T &>()))>;// ... which can be dereferenced
template<typename, typename = void> struct is_iterable : std::false_type {};
// specialization
template<class T> struct is_iterable<T, check_specs<T>> : std::true_type {};
}// namespace is_iterable_impl
template<class T> using is_iterable = is_iterable_impl::is_iterable<T>;
template<typename T> constexpr bool is_iterable_v = is_iterable<T>::value;
// Source: https://stackoverflow.com/a/53429396/6793559

template<typename T>
using is_string =
    std::disjunction<std::is_same<char *, typename std::decay_t<T>>,
                     std::is_same<const char *, typename std::decay_t<T>>,
                     std::is_same<std::string, typename std::decay_t<T>>>;
template<typename T> constexpr bool is_string_v = is_string<T>::value;
// Source: https://stackoverflow.com/a/57812868/6793559

template<template<typename...> typename Target, typename Aux, typename... Ts>
struct is_specialized_for_impl : std::false_type {};

template<template<typename...> typename Target, typename... Args>
struct is_specialized_for_impl<Target, decltype(sizeof(Target<Args...>)),
                               Args...> : std::true_type {};

template<template<typename...> typename Target, typename... Args>
using is_specialized_for =
    is_specialized_for_impl<Target, std::size_t, Args...>;
template<template<typename...> typename Target, typename... Args>
constexpr bool is_specialized_for_v =
    is_specialized_for<Target, Args...>::value;

template<typename T>
using is_tuple_like = is_specialized_for<std::tuple_size, T>;
template<typename T> constexpr bool is_tuple_like_v = is_tuple_like<T>::value;

template<typename T, typename = void> struct remove_all_extents_ {
  typedef std::remove_reference_t<T> type;
};

template<typename T>
struct remove_all_extents_<T, std::void_t<decltype(std::declval<T>()[0])>> {
  typedef
      typename remove_all_extents_<decltype(std::declval<T>()[0])>::type type;
};

template<typename T, typename = void>
struct rank_ : public std::integral_constant<std::size_t, 0> {};

template<typename T>
struct rank_<T, std::void_t<decltype(std::declval<T>()[0])>>
    : public std::integral_constant<
          std::size_t, rank_<decltype(std::declval<T>()[0])>::value + 1> {};
#endif
#endif// JHELPER_EXAMPLE_PROJECT_TASKS_TYPE_TRAITS_HPP_


struct fast_ios {
  fast_ios() {
#ifndef INTERACTIVE_MODE
    std::cin.tie(nullptr);
#endif
    std::ios::sync_with_stdio(false);
    std::cout.precision(15);
    std::cout << std::fixed;
  };
} const fast_ios_;

namespace io {
template<typename T, typename U>
std::ostream &operator<<(std::ostream &out, const std::pair<T, U> &p);
template<typename... Ts>
std::istream &operator>>(std::istream &in, std::tuple<Ts...> &t);
template<typename... Ts>
std::ostream &operator<<(std::ostream &, const std::tuple<Ts...> &);

template<typename T, typename U>
std::istream &operator>>(std::istream &in, std::pair<T, U> &p) {
  in >> p.first >> p.second;
  return in;
}

template<typename T>
std::istream &operator>>(std::istream &stream, std::vector<T> &vec) {
  for (auto &x : vec)
    stream >> x;
  return stream;
}

#if __cplusplus >= 201703L
template<typename... Ts>
std::istream &operator>>(std::istream &in, std::tuple<Ts...> &t) {
  std::apply([&in](auto &...args) { ((in >> args), ...); }, t);
  return in;
}

template<class... Args> void scan(Args &...args) {
  ((std::cin >> args), ...);
}

template<typename Container,
         typename = std::enable_if_t<std::conjunction_v<
             is_iterable<Container>, std::negation<is_string<Container>>>>>
std::ostream &operator<<(std::ostream &out, const Container &container) {
  using std::begin;
  using value_type =
      std::remove_reference_t<decltype(*begin(std::declval<Container &>()))>;
  constexpr char delimiter =
      is_iterable_v<value_type> or is_tuple_like_v<value_type> ? '\n' : ' ';
  bool first = true;
  for (auto &element : container) {
    if (first)
      first = false;
    else
      out << delimiter;
    out << element;
  }
  return out;
}

// Source: https://en.cppreference.com/w/cpp/utility/apply
template<typename... Ts>
std::ostream &operator<<(std::ostream &out, const std::tuple<Ts...> &theTuple) {
  std::apply(
      [&out](Ts const &...tupleArgs) {
        std::size_t n{0};
        ((out << tupleArgs << (++n != sizeof...(Ts) ? " " : "")), ...);
      },
      theTuple);
  return out;
}
#endif

template<typename T, typename U>
std::ostream &operator<<(std::ostream &out, const std::pair<T, U> &p) {
  out << p.first << ' ' << p.second;
  return out;
}

template<typename T>
std::ostream &operator<<(std::ostream &out,
                         const std::vector<std::vector<T>> &t) {
  bool is_first = true;
  for (const auto &row : t) {
    if (is_first)
      is_first = false;
    else
      out << '\n';
    out << row;
  }
  return out;
}

std::ostream &operator<<(std::ostream &os, __int128 n) {
  if (n < 0) {
    n = -n;
    os << '-';
  }
  std::string s;
  while (n > 0) {
    s += char('0' + n % 10);
    n /= 10;
  }
  for (int i = (int) s.size() - 1; i >= 0; i--)
    os << s[i];
  return os;
}

#if __cplusplus >= 201703L
template<typename... Args> void pt(Args &&...args) {
  ((std::cout << args << ' '), ...);
}

template<typename First, typename... Args>
void pl(const First &first, const Args &...args) {
  std::cout << first;
  ((std::cout << ' ' << args), ...);
  std::cout << '\n';
}

template<typename... Args> void pn(const Args &...args) {
  ((std::cout << args << '\n'), ...);
}
#endif
}// namespace io
#endif// JHELPER_EXAMPLE_PROJECT_LIBRARY_IO_HPP_

//
// Created by zjsdu on 10/26/2020.
//
#ifndef JHELPER_EXAMPLE_PROJECT_LIBRARY_NDARRAY_HPP_
#define JHELPER_EXAMPLE_PROJECT_LIBRARY_NDARRAY_HPP_

template<typename T, unsigned Dimension> struct ndvec {
  using type = std::vector<typename ndvec<T, Dimension - 1>::type>;
};

template<typename T> struct ndvec<T, 0> { using type = T; };

// arbitrary-dimensional array that allows non-constexpr extents.
// Usage: ndarray<dimension, value_type> arr(extents..., init_value);
// An initial value for all array items can be specified if all extensions are
// specified.
// Examples:
// ndarray<2, int> a(2, 3, -1);
// ndarray<3, int> b(2, 3, 4);
// ndarray<3, int> c(2, 3);
template<unsigned dimension, typename T>
class ndarray : public ndvec<T, dimension>::type {
  using base_type = typename ndvec<T, dimension>::type;
  using value_type = typename base_type::value_type;
  using base_type::base_type;

 public:
  template<typename... Args>
  ndarray(unsigned d, Args... args)
      : std::vector<value_type>(d, ndarray<dimension - 1, T>(args...)) {}
};

template<typename T> class ndarray<1, T> : public std::vector<T> {
  using std::vector<T>::vector;
};
#endif// JHELPER_EXAMPLE_PROJECT_LIBRARY_NDARRAY_HPP_

//
// Created by zjsdu on 2/9/2021.
//

#ifndef JHELPER_EXAMPLE_PROJECT_LIBRARY_MACROS_H_
#define JHELPER_EXAMPLE_PROJECT_LIBRARY_MACROS_H_

#define CALL_WITH_EXPANDED_ARGS(function, ...) function(__VA_ARGS__)

#define JOIN_IMPL(arg1, arg2) arg1##arg2
#define JOIN(arg1, arg2) JOIN_IMPL(arg1, arg2)

#define EXPAND_1(...) __VA_ARGS__
#define EXPAND_4(...) EXPAND_1(EXPAND_1(EXPAND_1(__VA_ARGS__)))
#define EXPAND_13(...) EXPAND_4(EXPAND_4(EXPAND_4(__VA_ARGS__)))

#define PAUSE
#define COMMA() ,
#define TERMINATE(...)
#define SELECT_SECOND_ARG(arg1, arg2, ...) arg2
#define CONDITIONAL(peek, arg1, arg2)                                          \
  CALL_WITH_EXPANDED_ARGS(SELECT_SECOND_ARG, COMMA peek arg1, arg2)
#define TERMINATE_OR(peek, arg) CONDITIONAL(peek, TERMINATE, arg)

#define FOR_EACH_2_IMPL0(function, arg1, arg2, peek, ...)                      \
  function(arg1, arg2) TERMINATE_OR(peek, FOR_EACH_2_IMPL1)                    \
      PAUSE(function, peek, __VA_ARGS__)

#define FOR_EACH_2_IMPL1(function, arg1, arg2, peek, ...)                      \
  function(arg1, arg2) TERMINATE_OR(peek, FOR_EACH_2_IMPL0)                    \
      PAUSE(function, peek, __VA_ARGS__)

#define FOR_EACH_2(function, ...)                                              \
  EXPAND_13(FOR_EACH_2_IMPL0(function, __VA_ARGS__, ()))

#endif// JHELPER_EXAMPLE_PROJECT_LIBRARY_MACROS_H_

using ll = long long;
using ull = unsigned long long;
using i128 = __int128;
using vl = std::vector<ll>;
using vb = std::vector<bool>;
using vi = std::vector<int>;
using vs = std::vector<std::string>;
using pii = std::pair<int, int>;
using pli = std::pair<ll, int>;
using pil = std::pair<int, ll>;
using pll = std::pair<ll, ll>;
using vii = std::vector<pii>;
template<typename T>
using pq = std::priority_queue<T>;
template<typename T>
using min_pq = std::priority_queue<T, std::vector<T>, std::greater<T>>;
template<typename... Ts> using vt = std::vector<std::tuple<Ts...>>;
template<typename T> using vv = ndarray<2, T>;
template<typename T> struct range_tuple {
  const T &ref = beg;
  T beg;
  const T end;
  range_tuple(T b, T e) : beg(b), end(e) {}
};
#define rng4(i, a, b, c)                                                       \
  for (auto &&[i, JOIN(iter_, __LINE__), JOIN(end_, __LINE__)] =               \
           range_tuple<std::common_type<decltype(a), decltype(b)>::type>(a,    \
                                                                         b);   \
       i < JOIN(end_, __LINE__); JOIN(iter_, __LINE__) += c)
#define rng3(i, a, b) rng4(i, a, b, 1)
#define rng2(i, n) rng3(i, 0, n)
#define GET4(_1, _2, _3, _4, NAME, ...) NAME
#define rng(...) GET4(__VA_ARGS__, rng4, rng3, rng2)(__VA_ARGS__)
#define up4(i, a, b, c) rng (i, a, b + 1, c)
#define up3(i, a, b) up4(i, a, b, 1)
#define up(...) GET4(__VA_ARGS__, up4, up3, NO_IMPL)(__VA_ARGS__)
#define down4(i, b, a, c)                                                      \
  for (auto &&[i, JOIN(iter_, __LINE__), JOIN(end_, __LINE__)] =               \
           range_tuple<std::common_type<decltype(a), decltype(b)>::type>(b,    \
                                                                         a);   \
       i >= JOIN(end_, __LINE__); JOIN(iter_, __LINE__) -= c)
#define down3(i, b, a) down4(i, b, a, 1)
#define down(...) GET4(__VA_ARGS__, down4, down3, NO_IMPL)(__VA_ARGS__)
#define rep(n)                                                                 \
  for (auto JOIN(_iter_, __LINE__) = n; JOIN(_iter_, __LINE__) > 0;            \
       --JOIN(_iter_, __LINE__))
#define FOR_LAST_OPERATION_IMPL(arg1, arg2) arg1] : arg2
#define FOR_NORMAL_OPERATION_IMPL(arg1, arg2) arg1,
#define FOR_IMPL0(arg1, arg2, peek, ...)                                       \
  CONDITIONAL(peek, FOR_LAST_OPERATION_IMPL, FOR_NORMAL_OPERATION_IMPL)        \
  (arg1, arg2) TERMINATE_OR(peek, FOR_IMPL1) PAUSE(arg2, peek, __VA_ARGS__)
#define FOR_IMPL1(arg1, arg2, peek, ...)                                       \
  CONDITIONAL(peek, FOR_LAST_OPERATION_IMPL, FOR_NORMAL_OPERATION_IMPL)        \
  (arg1, arg2) TERMINATE_OR(peek, FOR_IMPL0) PAUSE(arg2, peek, __VA_ARGS__)
#define FOR_IMPL3(arg1, arg2, peek, ...)                                       \
  CONDITIONAL(peek, for (auto && arg1 : arg2),                                 \
  for (auto && [EXPAND_13(FOR_IMPL0(arg1, arg2, peek, __VA_ARGS__))))
#define FOR(...) FOR_IMPL3(__VA_ARGS__, ())
#define ALL(x) std::begin(x), std::end(x)
// hat off to 300iq
#define RALL(x) std::rbegin(x), std::rend(x)
#define pb push_back
#define eb emplace_back
#define MP make_pair
#define ep emplace
#define SZ(x) (int) (x).size()
#define rp(...) return pl(__VA_ARGS__)
#define rpn(...) return pn(__VA_ARGS__)
#define adv(i, n)                                                              \
  for (auto JOIN(_n_, __LINE__) = n; i < JOIN(_n_, __LINE__); ++i)
#define radv(i, n)                                                             \
  for (auto JOIN(_n_, __LINE__) = n; i > JOIN(_n_, __LINE__); --i)
#define INT(...)                                                               \
  int __VA_ARGS__;                                                             \
  io::scan(__VA_ARGS__)
#define LL(...)                                                                \
  long long __VA_ARGS__;                                                       \
  io::scan(__VA_ARGS__)
#define STR(...)                                                               \
  std::string __VA_ARGS__;                                                     \
  io::scan(__VA_ARGS__)
#define CHAR(...)                                                              \
  char __VA_ARGS__;                                                            \
  io::scan(__VA_ARGS__)
#define NL                                                                     \
  [] {                                                                         \
    std::cout << '\n';                                                         \
  }()
#define RI                                                                     \
  ([] {                                                                        \
    int x;                                                                     \
    std::cin >> x;                                                             \
    return x;                                                                  \
  })()
#define READ_VI(NAME, LEN)                                                     \
  std::vector<int> NAME(LEN);                                                  \
  io::scan(NAME);
#define VI(...) FOR_EACH_2(READ_VI, __VA_ARGS__)
#define READ_VII(NAME, LEN)                                                    \
  std::vector<std::pair<int, int>> NAME(LEN);                                  \
  io::scan(NAME);
#define VII(...) FOR_EACH_2(READ_VII, __VA_ARGS__)
#define READ_VL(NAME, LEN)                                                     \
  std::vector<long long> NAME(LEN);                                            \
  io::scan(NAME);
#define VL(...) FOR_EACH_2(READ_VL, __VA_ARGS__)
#define READ_VS(NAME, LEN)                                                     \
  std::vector<std::string> NAME(LEN);                                          \
  io::scan(NAME);
#define VS(...) FOR_EACH_2(READ_VS, __VA_ARGS__)
#endif// JHELPER_EXAMPLE_PROJECT_LIBRARY_ALIAS_HPP_

#ifndef CP_UTILS
#define CP_UTILS
#include <algorithm>
#include <bitset>
#include <climits>
#include <cmath>
#include <cstring>
#include <map>
#include <unordered_map>
#include <numeric>
#include <set>
#include <random>
#include <chrono>




inline void Yn(bool p) {
  std::cout << (p ? "Yes\n" : "No\n");
}
inline void YN(bool p) {
  std::cout << (p ? "YES\n" : "NO\n");
}
inline void yn(bool p) {
  std::cout << (p ? "yes\n" : "no\n");
}
template<typename Container> Container inc(Container &&c) {
  for (auto &e : c)
    ++e;
  return std::forward<Container>(c);
}
template<typename Container> Container dec(Container &&c) {
  for (auto &e : c)
    --e;
  return std::forward<Container>(c);
}

template<typename A, typename B>
bool chkmin(A& a, const B& b) {
  if (b < a) {
    a = b;
    return true;
  }
  return false;
}

template<typename A, typename B>
bool chkmax(A& a, const B& b) {
  if (a < b) {
    a = b;
    return true;
  }
  return false;
}

#if __cplusplus >= 201703L
template<typename A, typename B, typename... C>
bool chkmin(A& a, const B& b, const C&... c) {
  if (B res = std::min<B>({b, c...}); res < a) {
    a = res;
    return true;
  }
  return false;
}

template<typename A, typename B, typename... C>
bool chkmax(A& a, const B& b, const C&... c) {
  if (B res = std::max<B>({b, c...}); res > a) {
    a = res;
    return true;
  }
  return false;
}
#endif

template<typename T, typename U>
void append(T &container1, const U &container2) {
  container1.insert(container1.end(), container2.begin(), container2.end());
}

template<typename T> int argmin(const std::vector<T> &a) {
  return (int) (std::min_element(a.begin(), a.end()) - a.begin());
}

template<typename T> int argmax(const std::vector<T> &a) {
  return (int) (std::max_element(a.begin(), a.end()) - a.begin());
}

template<typename Container> Container reverse(Container &&c) {
  std::reverse(std::begin(c), std::end(c));
  return std::forward<Container>(c);
}

template<typename Sequence> Sequence rev_copy(Sequence a) {
  std::reverse(std::begin(a), std::end(a));
  return a;
}

template<typename Sequence> Sequence uniq(Sequence &&s) {
  std::sort(std::begin(s), std::end(s));
  s.erase(std::unique(std::begin(s), std::end(s)), std::end(s));
  return std::forward<Sequence>(s);
}

template<typename Container> auto max(const Container &c) {
  assert(c.size() > 0);
  return *std::max_element(std::begin(c), std::end(c));
}

template<typename Container> auto min(const Container &c) {
  assert(c.size() > 0);
  return *std::min_element(std::begin(c), std::end(c));
}

template<typename Array> int maxi(const Array &a) {
  assert(a.size() > 0);
  return int(std::max_element(std::begin(a), std::end(a)) - std::begin(a));
}

template<typename Array> int mini(const Array &a) {
  assert(a.size() > 0);
  return int(std::min_element(std::begin(a), std::end(a)) - std::begin(a));
}

template<typename Array, typename Value> auto lb(const Array &a, Value v) {
  return std::lower_bound(std::begin(a), std::end(a), v);
}

template<typename Array, typename Value> auto ub(const Array &a, Value v) {
  return std::upper_bound(std::begin(a), std::end(a), v);
}

template<typename Array, typename Value, typename Compare>
auto lb(const Array &a, Value v, Compare compare) {
  return std::lower_bound(std::begin(a), std::end(a), v, compare);
}

template<typename Array, typename Value, typename Compare>
auto ub(const Array &a, Value v, Compare compare) {
  return std::upper_bound(std::begin(a), std::end(a), v, compare);
}

template<typename Array, typename Value> int lbi(const Array &a, Value v) {
  return int(lb(a, v) - std::begin(a));
}

template<typename Iter, typename Value> int lbi(Iter beg, int count, Value v) {
  assert(count > 0);
  return int(std::lower_bound(beg, beg + count, v) - beg);
}

template<typename Iter, typename Value> int ubi(Iter beg, int count, Value v) {
  assert(count > 0);
  return int(std::upper_bound(beg, beg + count, v) - beg);
}

template<typename Array, typename Value> int ubi(const Array &a, Value v) {
  return int(ub(a, v) - std::begin(a));
}

template<typename Container>
Container iota(Container &&c, value_type_of<Container> v) {
  std::iota(std::begin(c), std::end(c), v);
  return std::forward<Container>(c);
}

template<typename T, typename Comp>
std::vector<int> argsort(const std::vector<T> &array, Comp comp) {
  std::vector<int> res(array.size());
  std::iota(res.begin(), res.end(), 0);
  std::stable_sort(res.begin(), res.end(), [&array, comp](int i, int j) {
    return comp(array[i], array[j]);
  });
  return res;
}

template<typename T> std::vector<int> argsort(const std::vector<T>& array) {
  std::vector<int> res(array.size());
  std::iota(res.begin(), res.end(), 0);
  std::stable_sort(res.begin(), res.end(),
                   [&array](int i, int j) { return array[i] < array[j]; });
  return res;
}

template<typename T> std::vector<int> order(const std::vector<T>& array) {
  int n = (int) array.size();
  std::vector<int> I(n);
  std::iota(I.begin(), I.end(), 0);
  std::sort(I.begin(), I.end(),
            [&array](int i, int j) { return array[i] < array[j]; });
  std::vector<int> order(n);
  for (int i = 1; i < n; i++)
    order[I[i]] = order[I[i - 1]] + (array[I[i - 1]] < array[I[i]]);
  return order;
}

#if __cplusplus >=201703L
template<typename Container, typename Compare = void *>
Container sort(Container &&c, Compare comp = nullptr) {
  if constexpr (std::is_same_v<Compare, void *>)
    std::sort(std::begin(c), std::end(c));
  else
    std::sort(std::begin(c), std::end(c), comp);
  return std::forward<Container>(c);
}
#endif

template<typename T> struct reversion_wrapper { T &iterable; };
template<typename T> auto begin(reversion_wrapper<T> w) {
  using std::rbegin;
  return rbegin(w.iterable);
}
template<typename T> auto end(reversion_wrapper<T> w) {
  using std::rend;
  return rend(w.iterable);
}
template<typename T> reversion_wrapper<T> rev_view(T &&iterable) {
  return {std::forward<T>(iterable)};
}

/// @return nearest integer not less than the quotient x/y.
template<typename T, typename U> T qceil(T x, U y) {
  assert(y > 0);
  T q = x / y;
  return q + (q * y < x);
}

/// @return nearest integer not greater than the quotient x/y.
template<typename T, typename U> T qfloor(T x, U y) {
  assert(y > 0);
  T q = x / y;
  return q - (q * y > x);
}

template<typename T, typename U> std::pair<T, U> divmod(T x, U y) {
  assert(y > 0);
  T q = qfloor(x, y);
  return {q, x - q * y};
};

/// @return nearest multiple of y not less than x.
template<typename T, typename U> T mceil(T x, U y) {
  assert(y > 0);
  return qceil(x, y) * y;
}

/// @return nearest multiple of y not greater than x.
template<typename T, typename U> T mfloor(T x, U y) {
  assert(y > 0);
  return qfloor(x, y) * y;
}

#if __cplusplus >= 201703L
template<class...> struct typelist {};

template<class T, class... Ts>
constexpr bool any_same = (std::is_same<T, Ts>::value || ...);

template<class F> struct y_combinator {
  template<class... TLs> struct ref {
    y_combinator &self;
    template<class... Args> decltype(auto) operator()(Args &&...args) const {
      using G = std::conditional_t<any_same<typelist<Args...>, TLs...>,
                                   ref<TLs...>, ref<TLs..., typelist<Args...>>>;
      return self.f(G{self}, std::forward<Args>(args)...);
    }
  };
  F f;
  template<class... Args> decltype(auto) operator()(Args &&...args) {
    return ref<>{*this}(std::forward<Args>(args)...);
  }
};
template<class F> y_combinator(F) -> y_combinator<F>;
#endif

template<typename T> constexpr T INF = std::numeric_limits<T>::max() / 2;

/// @brief Usage: acc\<type_of_sum\>(array)
template<typename T, typename U> T acc(const U& array) {
  return std::accumulate(std::begin(array), std::end(array), T(0));
}

template <typename T> T acc(const std::vector<T>& array) {
  return std::accumulate(array.begin(), array.end(), T(0));
}

// maps values of a into 0, 1, 2, ..., preserving order.
template<typename T> std::vector<int> normalize(const std::vector<T> &a) {
  assert(not a.empty());
  int n = (int) a.size();
  std::vector<int> I = argsort(a);
  std::vector<int> b(a.size());
  b[I[0]] = 0;
  for (int i = 1; i < n; i++)
    b[I[i]] = b[I[i - 1]] + (a[I[i - 1]] < a[I[i]]);
  return b;
}

template<typename F, typename Int>
Int binary_search(F check, Int ok, Int ng, bool check_ok = true) {
  if (check_ok)
    assert(check(ok));
  while (std::abs(ok - ng) > 1) {
    Int x = ng + (ok - ng) / 2;
    (check(x) ? ok : ng) = x;
  }
  return ok;
}

template<typename T, typename Int> int bit(T a, Int i) {
  return a >> i & 1;
}

#define popcnt(x) __builtin_popcountll((x))

// sign used in principle of inclusion-exclusion
int pie_sign(int s) {
  assert(s >= 0);
  return popcnt(s) & 1 ? -1 : 1;
}

#endif// CP_UTILS

//
// Created by zjs on 12/19/23.
//

#ifndef JHELPER_EXAMPLE_PROJECT_LIBRARY_LEVEL_ANCESTOR_HPP_
#define JHELPER_EXAMPLE_PROJECT_LIBRARY_LEVEL_ANCESTOR_HPP_

class level_ancestor {
  int n;
  int log;
  std::vector<std::vector<int>> a;
 public:
  explicit level_ancestor(const std::vector<int> &parent)
      : n((int) parent.size()) {
    log = 0;
    int t = 1;
    while (t < n) {
      log++;
      t *= 2;
    }
    a.assign(log, std::vector<int>(n, -1));
    if (log) {
      a[0] = parent;
      for (int i = 1; i < log; i++)
        for (int j = 0; j < n; j++)
          if (a[i - 1][j] != -1)
            a[i][j] = a[i - 1][a[i - 1][j]];
    }
  }

  int ancestor(int u, int k) const {
    if (k >= n)
      return -1;
    int v = u;
    for (int i = 0; i < log; i++)
      if (k >> i & 1) {
        v = a[i][v];
        if (v == -1)
          break;
      }
    return v;
  }
};
#endif// JHELPER_EXAMPLE_PROJECT_LIBRARY_LEVEL_ANCESTOR_HPP_

using namespace io;
using namespace std;

struct lazy_fenwick {
  int n;
  pii e = {0, -1};
  unordered_map<int, pii> a;
  void update(int i, pii x) {
    while (i <= n) {
      if (a.count(i))
        a[i] = max(a[i], x);
      else
        a[i] = x;
      i += i & -i;
    }
  }
  pii sum(int i) {
    pii res = e;
    while (i) {
      auto it = a.find(i);
      if (it != a.end())
        res = max(res, it->second);
      i -= i & -i;
    }
    return res;
  }
  // n is the upper bound of keys
  lazy_fenwick(int n) : n(n) {}
};
void solve() {
  // 树形结构
  INT(n, k);
  vii a(n);
  scan(a);
  sort(a);
  debug(a);
  vi pa(n);
  lazy_fenwick b(1e9);
  rng (i, n) {
    auto [l, r] = a[i];
    auto res = b.sum(l);
    pa[i] = res.second;
    b.update(r, {l, i});
  }
  debug(pa);
  level_ancestor la(pa);
  int ans = INT_MAX;
  rng (i, n) {
    int j = la.ancestor(i, k - 1);
    debug(j);
    if (j != -1) {
      chkmin(ans, a[i].second - a[j].first);
    }
  }
  if (ans == INT_MAX) ans = -1;
  pl(ans);
}

#include <iostream>

int main() {
#if defined FILE_IO and not defined LOCAL
  freopen(FILE_IO ".in", "r", stdin);
  freopen(FILE_IO ".out", "w", stdout);
#endif
  solve();
  return 0;
}