#include <ostream>
#include <unordered_map>
#include <bitset>
#include <stack>
#include <utility>
#include <iterator>
#include <vector>
#include <type_traits>
#include <array>
#include <deque>
#include <map>
#include <cassert>
#include <numeric>
#include <fstream>
#include <algorithm>
#include <functional>
#include <optional>
#include <set>
#include <iostream>
#include <string>
#include <unordered_set>
#include <queue>
#include <istream>
#include <iomanip>

#ifndef KK2_TEMPLATE_PROCON_HPP
#define KK2_TEMPLATE_PROCON_HPP 1


#ifndef KK2_TEMPLATE_CONSTANT_HPP
#define KK2_TEMPLATE_CONSTANT_HPP 1

#ifndef KK2_TEMPLATE_TYPE_ALIAS_HPP
#define KK2_TEMPLATE_TYPE_ALIAS_HPP 1


using u32 = unsigned int;
using i64 = long long;
using u64 = unsigned long long;
using i128 = __int128_t;
using u128 = __uint128_t;

using pi = std::pair<int, int>;
using pl = std::pair<i64, i64>;
using pil = std::pair<int, i64>;
using pli = std::pair<i64, int>;

template <class T> using vc = std::vector<T>;
template <class T> using vvc = std::vector<vc<T>>;
template <class T> using vvvc = std::vector<vvc<T>>;
template <class T> using vvvvc = std::vector<vvvc<T>>;

template <class T> using pq = std::priority_queue<T>;
template <class T> using pqi = std::priority_queue<T, std::vector<T>, std::greater<T>>;

#endif // KK2_TEMPLATE_TYPE_ALIAS_HPP

template <class T> constexpr T infty = 0;
template <> constexpr int infty<int> = (1 << 30) - 123;
template <> constexpr i64 infty<i64> = (1ll << 62) - (1ll << 31);
template <> constexpr i128 infty<i128> = (i128(1) << 126) - (i128(1) << 63);
template <> constexpr u32 infty<u32> = infty<int>;
template <> constexpr u64 infty<u64> = infty<i64>;
template <> constexpr u128 infty<u128> = infty<i128>;
template <> constexpr double infty<double> = infty<i64>;
template <> constexpr long double infty<long double> = infty<i64>;

constexpr int mod = 998244353;
constexpr int modu = 1e9 + 7;
constexpr long double PI = 3.14159265358979323846;

#endif // KK2_TEMPLATE_CONSTANT_HPP
#ifndef KK2_TEMPLATE_FUNCTION_UTIL_HPP
#define KK2_TEMPLATE_FUNCTION_UTIL_HPP 1


namespace kk2 {

template <class T, class... Sizes> auto make_vector(int first, Sizes... sizes) {
    if constexpr (sizeof...(sizes) == 0) {
        return std::vector<T>(first);
    } else {
        return std::vector<decltype(make_vector<T>(sizes...))>(first, make_vector<T>(sizes...));
    }
}

template <class T, class U> void fill_all(std::vector<T> &v, const U &x) {
    std::fill(std::begin(v), std::end(v), T(x));
}

template <class T, class U> void fill_all(std::vector<std::vector<T>> &v, const U &x) {
    for (auto &u : v) fill_all(u, x);
}

template <class C> int mysize(const C &c) {
    return c.size();
}

// T: comutative monoid
template <class T, class U> U all_sum(const std::vector<T> &v, U init, U = U()) {
    U res = init;
    for (const auto &x : v) res += x;
    return res;
}

template <class T, class U> U all_sum(const std::vector<std::vector<T>> &v, U init, U unit = U()) {
    U res = init;
    for (const auto &u : v) res += all_sum(u, unit, unit);
    return res;
}

// T: commutative monoid, F: (U, T) -> U
template <class T, class U, class F> U all_prod(const std::vector<T> &v, U init, const F &f, U = U()) {
    U res = init;
    for (const auto &x : v) res = f(res, x);
    return res;
}

template <class T, class U, class F>
U all_prod(const std::vector<std::vector<T>> &v, U init, const F &f, U unit) {
    U res = init;
    for (const auto &u : v) res = f(res, all_prod(u, unit, f, unit));
    return res;
}

template <class T> T all_min(const std::vector<T> &v) {
    if (v.empty()) return T();
    T res = v[0];
    for (const auto &x : v) res = res > x ? x : res;
    return res;
}

template <class T>
T all_min(const std::vector<std::vector<T>> &v) {
    T res{};
    bool first = true;
    for (const auto &u : v) {
        if (u.empty()) continue;
        if (first) {
            res = all_min(u);
            first = false;
        } else {
            T tmp = all_min(u);
            res = res > tmp ? tmp : res;
        }
    }
    return res;
}

template <class T> T all_max(const std::vector<T> &v) {
    if (v.empty()) return T();
    T res = v[0];
    for (const auto &x : v) res = res < x ? x : res;
    return res;
}

template <class T>
T all_max(const std::vector<std::vector<T>> &v) {
    T res{};
    bool first = true;
    for (const auto &u : v) {
        if (u.empty()) continue;
        if (first) {
            res = all_max(u);
            first = false;
        } else {
            T tmp = all_max(u);
            res = res < tmp ? tmp : res;
        }
    }
    return res;
}

} // namespace kk2

#endif // KK2_TEMPLATE_FUNCTION_UTIL_HPP
#ifndef KK2_TEMPLATE_IO_UTIL_HPP
#define KK2_TEMPLATE_IO_UTIL_HPP 1


#ifndef KK2_TYPE_TRAITS_TYPE_TRAITS_HPP
#define KK2_TYPE_TRAITS_TYPE_TRAITS_HPP 1



namespace kk2 {

#ifndef _MSC_VER

template <typename T>
using is_signed_int128 = typename std::conditional<std::is_same<T, __int128_t>::value
                                                       or std::is_same<T, __int128>::value,
                                                   std::true_type,
                                                   std::false_type>::type;

template <typename T>
using is_unsigned_int128 =
    typename std::conditional<std::is_same<T, __uint128_t>::value
                                  or std::is_same<T, unsigned __int128>::value,
                              std::true_type,
                              std::false_type>::type;

template <typename T>
using is_integral =
    typename std::conditional<std::is_integral<T>::value or is_signed_int128<T>::value
                                  or is_unsigned_int128<T>::value,
                              std::true_type,
                              std::false_type>::type;

template <typename T>
using is_signed = typename std::conditional<std::is_signed<T>::value or is_signed_int128<T>::value,
                                            std::true_type,
                                            std::false_type>::type;

template <typename T>
using is_unsigned =
    typename std::conditional<std::is_unsigned<T>::value or is_unsigned_int128<T>::value,
                              std::true_type,
                              std::false_type>::type;

template <typename T>
using make_unsigned_int128 =
    typename std::conditional<std::is_same<T, __int128_t>::value, __uint128_t, unsigned __int128>;

template <typename T>
using to_unsigned =
    typename std::conditional<is_signed_int128<T>::value,
                              make_unsigned_int128<T>,
                              typename std::conditional<std::is_signed<T>::value,
                                                        std::make_unsigned<T>,
                                                        std::common_type<T>>::type>::type;

#else

template <typename T> using is_integral = std::enable_if_t<std::is_integral<T>::value>;
template <typename T> using is_signed = std::enable_if_t<std::is_signed<T>::value>;
template <typename T> using is_unsigned = std::enable_if_t<std::is_unsigned<T>::value>;
template <typename T> using to_unsigned = std::make_unsigned<T>;

#endif // _MSC_VER

template <typename T> using is_integral_t = std::enable_if_t<is_integral<T>::value>;
template <typename T> using is_signed_t = std::enable_if_t<is_signed<T>::value>;
template <typename T> using is_unsigned_t = std::enable_if_t<is_unsigned<T>::value>;


template <typename T>
using is_function_pointer =
    typename std::conditional<std::is_pointer_v<T> && std::is_function_v<std::remove_pointer_t<T>>,
                              std::true_type,
                              std::false_type>::type;

template <typename T, std::enable_if_t<is_function_pointer<T>::value> * = nullptr>
struct is_two_args_function_pointer : std::false_type {};

template <typename R, typename T1, typename T2>
struct is_two_args_function_pointer<R (*)(T1, T2)> : std::true_type {};

template <typename T>
using is_two_args_function_pointer_t = std::enable_if_t<is_two_args_function_pointer<T>::value>;

namespace type_traits {

struct istream_tag {};

struct ostream_tag {};

} // namespace type_traits

template <typename T>
using is_standard_istream = typename std::conditional<std::is_same<T, std::istream>::value
                                                          || std::is_same<T, std::ifstream>::value,
                                                      std::true_type,
                                                      std::false_type>::type;
template <typename T>
using is_standard_ostream = typename std::conditional<std::is_same<T, std::ostream>::value
                                                          || std::is_same<T, std::ofstream>::value,
                                                      std::true_type,
                                                      std::false_type>::type;
template <typename T> using is_user_defined_istream = std::is_base_of<type_traits::istream_tag, T>;
template <typename T> using is_user_defined_ostream = std::is_base_of<type_traits::ostream_tag, T>;

template <typename T>
using is_istream =
    typename std::conditional<is_standard_istream<T>::value || is_user_defined_istream<T>::value,
                              std::true_type,
                              std::false_type>::type;

template <typename T>
using is_ostream =
    typename std::conditional<is_standard_ostream<T>::value || is_user_defined_ostream<T>::value,
                              std::true_type,
                              std::false_type>::type;

template <typename T> using is_istream_t = std::enable_if_t<is_istream<T>::value>;
template <typename T> using is_ostream_t = std::enable_if_t<is_ostream<T>::value>;


} // namespace kk2

#endif // KK2_TYPE_TRAITS_TYPE_TRAITS_HPP

// なんかoj verifyはプロトタイプ宣言が落ちる

namespace impl {

struct read {
    template <class IStream, class T>
    inline static void all_read(IStream &is, T &x) {
        is >> x;
    }

    template <class IStream, class T, class U>
    inline static void all_read(IStream &is, std::pair<T, U> &p) {
        all_read(is, p.first);
        all_read(is, p.second);
    }

    template <class IStream, class T>
    inline static void all_read(IStream &is, std::vector<T> &v) {
        for (T &x : v) all_read(is, x);
    }

    template <class IStream, class T, size_t F>
    inline static void all_read(IStream &is, std::array<T, F> &a) {
        for (T &x : a) all_read(is, x);
    }
};

struct write {
    template <class OStream, class T>
    inline static void all_write(OStream &os, const T &x) {
        os << x;
    }

    template <class OStream, class T, class U>
    inline static void all_write(OStream &os, const std::pair<T, U> &p) {
        all_write(os, p.first);
        all_write(os, ' ');
        all_write(os, p.second);
    }

    template <class OStream, class T>
    inline static void all_write(OStream &os, const std::vector<T> &v) {
        for (int i = 0; i < (int)v.size(); ++i) {
            if (i) all_write(os, ' ');
            all_write(os, v[i]);
        }
    }

    template <class OStream, class T, size_t F>
    inline static void all_write(OStream &os, const std::array<T, F> &a) {
        for (int i = 0; i < (int)F; ++i) {
            if (i) all_write(os, ' ');
            all_write(os, a[i]);
        }
    }
};

} // namespace impl

template <class IStream, class T, class U, kk2::is_istream_t<IStream> * = nullptr>
IStream &operator>>(IStream &is, std::pair<T, U> &p) {
    impl::read::all_read(is, p);
    return is;
}

template <class IStream, class T, kk2::is_istream_t<IStream> * = nullptr>
IStream &operator>>(IStream &is, std::vector<T> &v) {
    impl::read::all_read(is, v);
    return is;
}

template <class IStream, class T, size_t F, kk2::is_istream_t<IStream> * = nullptr>
IStream &operator>>(IStream &is, std::array<T, F> &a) {
    impl::read::all_read(is, a);
    return is;
}

template <class OStream, class T, class U, kk2::is_ostream_t<OStream> * = nullptr>
OStream &operator<<(OStream &os, const std::pair<T, U> &p) {
    impl::write::all_write(os, p);
    return os;
}

template <class OStream, class T, kk2::is_ostream_t<OStream> * = nullptr>
OStream &operator<<(OStream &os, const std::vector<T> &v) {
    impl::write::all_write(os, v);
    return os;
}

template <class OStream, class T, size_t F, kk2::is_ostream_t<OStream> * = nullptr>
OStream &operator<<(OStream &os, const std::array<T, F> &a) {
    impl::write::all_write(os, a);
    return os;
}

#endif // KK2_TEMPLATE_IO_UTIL_HPP
#ifndef KK2_TEMPLATE_MACROS_HPP
#define KK2_TEMPLATE_MACROS_HPP 1

#define rep1(a) for (long long _ = 0; _ < (long long)(a); ++_)
#define rep2(i, a) for (long long i = 0; i < (long long)(a); ++i)
#define rep3(i, a, b) for (long long i = (a); i < (long long)(b); ++i)
#define repi2(i, a) for (long long i = (a) - 1; i >= 0; --i)
#define repi3(i, a, b) for (long long i = (a) - 1; i >= (long long)(b); --i)
#define overload3(a, b, c, d, ...) d
#define rep(...) overload3(__VA_ARGS__, rep3, rep2, rep1)(__VA_ARGS__)
#define repi(...) overload3(__VA_ARGS__, repi3, repi2, rep1)(__VA_ARGS__)

#define fi first
#define se second
#define all(p) p.begin(), p.end()

#endif // KK2_TEMPLATE_MACROS_HPP

struct FastIOSetUp {
    FastIOSetUp() {
        std::ios::sync_with_stdio(false);
        std::cin.tie(nullptr);
    }
} fast_io_set_up;

auto &kin = std::cin;
auto &kout = std::cout;
auto (*kendl)(std::ostream &) = std::endl<char, std::char_traits<char>>;

void Yes(bool b = 1) {
    kout << (b ? "Yes\n" : "No\n");
}

void No(bool b = 1) {
    kout << (b ? "No\n" : "Yes\n");
}

void YES(bool b = 1) {
    kout << (b ? "YES\n" : "NO\n");
}

void NO(bool b = 1) {
    kout << (b ? "NO\n" : "YES\n");
}

void yes(bool b = 1) {
    kout << (b ? "yes\n" : "no\n");
}

void no(bool b = 1) {
    kout << (b ? "no\n" : "yes\n");
}

template <class T, class S> inline bool chmax(T &a, const S &b) {
    return (a < b ? a = b, 1 : 0);
}

template <class T, class S> inline bool chmin(T &a, const S &b) {
    return (a > b ? a = b, 1 : 0);
}

std::istream &operator>>(std::istream &is, u128 &x) {
    std::string s;
    is >> s;
    x = 0;
    for (char c : s) {
        assert('0' <= c && c <= '9');
        x = x * 10 + c - '0';
    }
    return is;
}

std::istream &operator>>(std::istream &is, i128 &x) {
    std::string s;
    is >> s;
    bool neg = s[0] == '-';
    x = 0;
    for (int i = neg; i < (int)s.size(); i++) {
        assert('0' <= s[i] && s[i] <= '9');
        x = x * 10 + s[i] - '0';
    }
    if (neg) x = -x;
    return is;
}

std::ostream &operator<<(std::ostream &os, u128 x) {
    if (x == 0) return os << '0';
    std::string s;
    while (x) {
        s.push_back('0' + x % 10);
        x /= 10;
    }
    std::reverse(s.begin(), s.end());
    return os << s;
}

std::ostream &operator<<(std::ostream &os, i128 x) {
    if (x == 0) return os << '0';
    if (x < 0) {
        os << '-';
        x = -x;
    }
    std::string s;
    while (x) {
        s.push_back('0' + x % 10);
        x /= 10;
    }
    std::reverse(s.begin(), s.end());
    return os << s;
}

#endif // KK2_TEMPLATE_PROCON_HPP
#ifndef KK2_TEMPLATE_DEBUG_HPP
#define KK2_TEMPLATE_DEBUG_HPP 1


#ifndef KK2_TYPE_TRAITS_MEMBER_HPP
#define KK2_TYPE_TRAITS_MEMBER_HPP 1



namespace kk2 {

#define HAS_MEMBER_FUNC(member)                                                                    \
    template <typename T, typename... Ts> struct has_member_func_##member##_impl {                 \
        template <typename U>                                                                      \
        static std::true_type check(decltype(std::declval<U>().member(std::declval<Ts>()...)) *);  \
        template <typename U> static std::false_type check(...);                                   \
        using type = decltype(check<T>(nullptr));                                                  \
    };                                                                                             \
    template <typename T, typename... Ts>                                                          \
    struct has_member_func_##member : has_member_func_##member##_impl<T, Ts...>::type {};          \
    template <typename T, typename... Ts>                                                          \
    using has_member_func_##member##_t =                                                           \
        std::enable_if_t<has_member_func_##member<T, Ts...>::value>;                               \
    template <typename T, typename... Ts>                                                          \
    using not_has_member_func_##member##_t =                                                       \
        std::enable_if_t<!has_member_func_##member<T, Ts...>::value>;

#define HAS_MEMBER_VAR(member)                                                                     \
    template <typename T> struct has_member_var_##member##_impl {                                  \
        template <typename U> static std::true_type check(decltype(std::declval<U>().member) *);   \
        template <typename U> static std::false_type check(...);                                   \
        using type = decltype(check<T>(nullptr));                                                  \
    };                                                                                             \
    template <typename T>                                                                          \
    struct has_member_var_##member : has_member_var_##member##_impl<T>::type {};                   \
    template <typename T>                                                                          \
    using has_member_var_##member##_t = std::enable_if_t<has_member_var_##member<T>::value>;       \
    template <typename T>                                                                          \
    using not_has_member_var_##member##_t = std::enable_if_t<!has_member_var_##member<T>::value>;

HAS_MEMBER_FUNC(debug_output)
HAS_MEMBER_FUNC(val)


#undef HAS_MEMBER_FUNC
#undef HAS_MEMBER_VAR
} // namespace kk2

#endif // KK2_TYPE_TRAITS_MEMBER_HPP

namespace kk2 {

namespace debug {

#ifdef KK2

template <class OStream, is_ostream_t<OStream> *> void output(OStream &os);

template <class OStream, class T, is_ostream_t<OStream> *> void output(OStream &os, const T &t);

template <class OStream, class T, is_ostream_t<OStream> *>
void output(OStream &os, const std::vector<T> &v);

template <class OStream, class T, is_ostream_t<OStream> *>
void output(OStream &os, const std::vector<std::vector<T>> &d);

template <class OStream, class T, size_t F, is_ostream_t<OStream> *>
void output(OStream &os, const std::array<T, F> &a);

template <class OStream, class T, class U, is_ostream_t<OStream> *>
void output(OStream &os, const std::pair<T, U> &p);

template <class OStream, class T, is_ostream_t<OStream> *>
void output(OStream &os, const std::queue<T> &q);

template <class OStream, class T, class Container, class Compare, is_ostream_t<OStream> *>
void output(OStream &os, const std::priority_queue<T, Container, Compare> &q);

template <class OStream, class T, is_ostream_t<OStream> *>
void output(OStream &os, const std::deque<T> &d);

template <class OStream, class T, is_ostream_t<OStream> *>
void output(OStream &os, const std::stack<T> &s);

template <class OStream, class Key, class Compare, class Allocator, is_ostream_t<OStream> *>
void output(OStream &os, const std::set<Key, Compare, Allocator> &s);

template <class OStream, class Key, class Compare, class Allocator, is_ostream_t<OStream> *>
void output(OStream &os, const std::multiset<Key, Compare, Allocator> &s);

template <class OStream,
          class Key,
          class Hash,
          class KeyEqual,
          class Allocator,
          is_ostream_t<OStream> *>
void output(OStream &os, const std::unordered_set<Key, Hash, KeyEqual, Allocator> &s);

template <class OStream,
          class Key,
          class Hash,
          class KeyEqual,
          class Allocator,
          is_ostream_t<OStream> *>
void output(OStream &os, const std::unordered_multiset<Key, Hash, KeyEqual, Allocator> &s);

template <class OStream,
          class Key,
          class T,
          class Compare,
          class Allocator,
          is_ostream_t<OStream> *>
void output(OStream &os, const std::map<Key, T, Compare, Allocator> &m);

template <class OStream,
          class Key,
          class T,
          class Hash,
          class KeyEqual,
          class Allocator,
          is_ostream_t<OStream> *>
void output(OStream &os, const std::unordered_map<Key, T, Hash, KeyEqual, Allocator> &m);

template <class OStream, is_ostream_t<OStream> * = nullptr> void output(OStream &) {
}

template <class OStream, class T, is_ostream_t<OStream> * = nullptr>
void output(OStream &os, const T &t) {
    if constexpr (has_member_func_debug_output<T, OStream &>::value) {
        t.debug_output(os);
    } else {
        os << t;
    }
}

template <class OStream, class T, is_ostream_t<OStream> * = nullptr>
void output(OStream &os, const std::vector<T> &v) {
    os << "[";
    for (int i = 0; i < (int)v.size(); i++) {
        output(os, v[i]);
        if (i + 1 != (int)v.size()) os << ", ";
    }
    os << "]";
}

template <class OStream, class T, is_ostream_t<OStream> * = nullptr>
void output(OStream &os, const std::vector<std::vector<T>> &d) {
    os << "[\n";
    for (int i = 0; i < (int)d.size(); i++) {
        output(os, d[i]);
        output(os, "\n");
    }
    os << "]";
}

template <class OStream, class T, size_t F, is_ostream_t<OStream> * = nullptr>
void output(OStream &os, const std::array<T, F> &a) {
    os << "[";
    for (int i = 0; i < (int)F; i++) {
        output(os, a[i]);
        if (i + 1 != (int)F) os << ", ";
    }
    os << "]";
}

template <class OStream, class T, class U, is_ostream_t<OStream> * = nullptr>
void output(OStream &os, const std::pair<T, U> &p) {
    os << "(";
    output(os, p.first);
    os << ", ";
    output(os, p.second);
    os << ")";
}

template <class OStream, class T, is_ostream_t<OStream> * = nullptr>
void output(OStream &os, const std::queue<T> &q) {
    os << "[";
    std::queue<T> tmp = q;
    while (!tmp.empty()) {
        output(os, tmp.front());
        tmp.pop();
        if (!tmp.empty()) os << ", ";
    }
    os << "]";
}

template <class OStream, class T, class Container, class Compare, is_ostream_t<OStream> * = nullptr>
void output(OStream &os, const std::priority_queue<T, Container, Compare> &q) {
    os << "[";
    std::priority_queue<T, Container, Compare> tmp = q;
    while (!tmp.empty()) {
        output(os, tmp.top());
        tmp.pop();
        if (!tmp.empty()) os << ", ";
    }
    os << "]";
}

template <class OStream, class T, is_ostream_t<OStream> * = nullptr>
void output(OStream &os, const std::deque<T> &d) {
    os << "[";
    std::deque<T> tmp = d;
    while (!tmp.empty()) {
        output(os, tmp.front());
        tmp.pop_front();
        if (!tmp.empty()) os << ", ";
    }
    os << "]";
}

template <class OStream, class T, is_ostream_t<OStream> * = nullptr>
void output(OStream &os, const std::stack<T> &s) {
    os << "[";
    std::stack<T> tmp = s;
    std::vector<T> v;
    while (!tmp.empty()) {
        v.push_back(tmp.top());
        tmp.pop();
    }
    for (int i = (int)v.size() - 1; i >= 0; i--) {
        output(os, v[i]);
        if (i != 0) os << ", ";
    }
    os << "]";
}

template <class OStream,
          class Key,
          class Compare,
          class Allocator,
          is_ostream_t<OStream> * = nullptr>
void output(OStream &os, const std::set<Key, Compare, Allocator> &s) {
    os << "{";
    std::set<Key, Compare, Allocator> tmp = s;
    for (auto it = tmp.begin(); it != tmp.end(); ++it) {
        output(os, *it);
        if (std::next(it) != tmp.end()) os << ", ";
    }
    os << "}";
}

template <class OStream,
          class Key,
          class Compare,
          class Allocator,
          is_ostream_t<OStream> * = nullptr>
void output(OStream &os, const std::multiset<Key, Compare, Allocator> &s) {
    os << "{";
    std::multiset<Key, Compare, Allocator> tmp = s;
    for (auto it = tmp.begin(); it != tmp.end(); ++it) {
        output(os, *it);
        if (std::next(it) != tmp.end()) os << ", ";
    }
    os << "}";
}

template <class OStream,
          class Key,
          class Hash,
          class KeyEqual,
          class Allocator,
          is_ostream_t<OStream> * = nullptr>
void output(OStream &os, const std::unordered_set<Key, Hash, KeyEqual, Allocator> &s) {
    os << "{";
    std::unordered_set<Key, Hash, KeyEqual, Allocator> tmp = s;
    for (auto it = tmp.begin(); it != tmp.end(); ++it) {
        output(os, *it);
        if (std::next(it) != tmp.end()) os << ", ";
    }
    os << "}";
}

template <class OStream,
          class Key,
          class Hash,
          class KeyEqual,
          class Allocator,
          is_ostream_t<OStream> * = nullptr>
void output(OStream &os, const std::unordered_multiset<Key, Hash, KeyEqual, Allocator> &s) {
    os << "{";
    std::unordered_multiset<Key, Hash, KeyEqual, Allocator> tmp = s;
    for (auto it = tmp.begin(); it != tmp.end(); ++it) {
        output(os, *it);
        if (std::next(it) != tmp.end()) os << ", ";
    }
    os << "}";
}

template <class OStream,
          class Key,
          class T,
          class Compare,
          class Allocator,
          is_ostream_t<OStream> * = nullptr>
void output(OStream &os, const std::map<Key, T, Compare, Allocator> &m) {
    os << "{";
    std::map<Key, T, Compare, Allocator> tmp = m;
    for (auto it = tmp.begin(); it != tmp.end(); ++it) {
        output(os, it->first);
        os << ": ";
        output(os, it->second);
        if (std::next(it) != tmp.end()) os << ", ";
    }
    os << "}";
}

template <class OStream,
          class Key,
          class T,
          class Hash,
          class KeyEqual,
          class Allocator,
          is_ostream_t<OStream> * = nullptr>
void output(OStream &os, const std::unordered_map<Key, T, Hash, KeyEqual, Allocator> &m) {
    os << "{";
    std::unordered_map<Key, T, Hash, KeyEqual, Allocator> tmp = m;
    for (auto it = tmp.begin(); it != tmp.end(); ++it) {
        output(os, it->first);
        os << ": ";
        output(os, it->second);
        if (std::next(it) != tmp.end()) os << ", ";
    }
    os << "}";
}

template <class OStream, class T, class... Args, is_ostream_t<OStream> * = nullptr>
void output(OStream &os, const T &t, const Args &...args) {
    output(os, t);
    os << ' ';
    output(os, args...);
}

template <class OStream, is_ostream_t<OStream> * = nullptr> void outputln(OStream &os) {
    os << '\n';
    os.flush();
}

template <class OStream, class T, class... Args, is_ostream_t<OStream> * = nullptr>
void outputln(OStream &os, const T &t, const Args &...args) {
    output(os, t, args...);
    os << '\n';
    os.flush();
}

#else

template <class OStream, class... Args, is_ostream_t<OStream> * = nullptr>
void output(OStream &, const Args &...) {
}

template <class OStream, class... Args, is_ostream_t<OStream> * = nullptr>
void outputln(OStream &, const Args &...) {
}

#endif // KK2

} // namespace debug

} // namespace kk2

#endif // KK2_TEMPLATE_DEBUG_HPP
#ifndef KK2_OTHERS_COORDINATE_COMPRESSION_HPP
#define KK2_OTHERS_COORDINATE_COMPRESSION_HPP 1


namespace kk2 {

// Coordinate Compression
template <typename S = int> struct CC {
    std::vector<S> xs;
    bool initialized;

    CC() : initialized(false) {}

    CC(const std::vector<S> &xs_) : xs(xs_), initialized(false) {}

    void add(S x) {
        xs.push_back(x);
        initialized = false;
    }

    void add(const std::vector<S> &ys) {
        std::copy(std::begin(ys), std::end(ys), std::back_inserter(xs));
        initialized = false;
    }

    void build() {
        std::sort(std::begin(xs), std::end(xs));
        xs.erase(std::unique(std::begin(xs), std::end(xs)), std::end(xs));
        initialized = true;
    }

    S operator[](int i) {
        if (!initialized) build();
        return xs[i];
    }

    int size() {
        if (!initialized) build();
        return xs.size();
    }

    int get(S x) {
        if (!initialized) build();
        return std::upper_bound(std::begin(xs), std::end(xs), x) - std::begin(xs) - 1;
    }

    std::vector<int> get(const std::vector<S> &ys) {
        std::vector<int> ret(ys.size());
        for (int i = 0; i < (int)ys.size(); ++i) ret[i] = get(ys[i]);
        return ret;
    }

    int operator()(S x) { return get(x); }

    std::vector<int> operator()(const std::vector<S> &ys) { return get(ys); }

    int lower(S x) {
        if (!initialized) build();
        return std::lower_bound(std::begin(xs), std::end(xs), x) - std::begin(xs);
    }

    int upper(S x) {
        if (!initialized) build();
        return std::upper_bound(std::begin(xs), std::end(xs), x) - std::begin(xs);
    }

    bool exist(S x) {
        if (!initialized) build();
        int idx = lower(x);
        return idx < (int)xs.size() && xs[idx] == x;
    }
};

} // namespace kk2

#endif // KK2_OTHERS_COORDINATE_COMPRESSION_HPP
#ifndef KK2_DATA_STRUCTURE_BINARY_INDEXED_TREE_HPP
#define KK2_DATA_STRUCTURE_BINARY_INDEXED_TREE_HPP 1


namespace kk2 {

template <typename T> struct BinaryIndexedTree {
    BinaryIndexedTree() : _n(0) {}

    BinaryIndexedTree(int n) : _n(n), data(n) {}

    void add(int p, T x) {
        assert(0 <= p && p < _n);
        for (p++; p <= _n; p += p & -p) data[p - 1] += x;
    }

    T sum(int l, int r) {
        assert(0 <= l && l <= r && r <= _n);
        return sum(r) - sum(l);
    }

    T get(int p) {
        assert(0 <= p && p < _n);
        return sum(p + 1) - sum(p);
    }

  private:
    int _n;
    std::vector<T> data;

    T sum(int r) {
        T s{};
        for (; r > 0; r -= r & -r) s += data[r - 1];
        return s;
    }
};

} // namespace kk2

#endif // #ifndef KK2_DATA_STRUCTURE_BINARY_INDEXED_TREE_HPP
using namespace std;

void solve() {
    /*
    座圧するだけ
    prefixとsuffixを求めよう
    */

    int n, q;
    kin >> n >> q;
    vector<i64> a(n);
    kin >> a;

    vc<i64> x(q);
    vvc<int> left(n), right(n);
    rep (i, q) {
        int l, r;
        i64 xx;
        kin >> l >> r >> xx;
        left[l - 1].push_back(i);
        right[r - 1].push_back(i);
        x[i] = xx;
    }

    vc<i64> res(q);
    kk2::CC<i64> cc(a);
    kk2::BinaryIndexedTree<int> count(cc.size());
    kk2::BinaryIndexedTree<i64> sum(cc.size());
    rep (i, n) {
        for (int idx : left[i]) {
            i64 xx = x[idx];
            int lw = cc.lower(xx);
            res[idx] -= 1ll * count.sum(0, lw) * xx - sum.sum(0, lw);
            res[idx] -= sum.sum(lw, cc.size()) - 1ll * count.sum(lw, cc.size()) * xx;
        }
        count.add(cc.get(a[i]), 1), sum.add(cc.get(a[i]), a[i]);
    }
    count = kk2::BinaryIndexedTree<int>(cc.size());
    sum = kk2::BinaryIndexedTree<i64>(cc.size());
    kk2::debug::outputln(kout, res);

    repi (i, n) {
        for (int idx : right[i]) {
            i64 xx = x[idx];
            int lw = cc.lower(xx);
            res[idx] -= 1ll * count.sum(0, lw) * xx - sum.sum(0, lw);
            res[idx] -= sum.sum(lw, cc.size()) - 1ll * count.sum(lw, cc.size()) * xx;
        }
        count.add(cc.get(a[i]), 1), sum.add(cc.get(a[i]), a[i]);
    }

    rep (i, q) {
        res[i] += 1ll * count.sum(0, cc.lower(x[i])) * x[i] - sum.sum(0, cc.lower(x[i]));
        res[i] += sum.sum(cc.lower(x[i]), cc.size()) - 1ll * count.sum(cc.lower(x[i]), cc.size()) * x[i];
    }
    rep (i, q) kout << res[i] << "\n";
}

int main() {
    int t = 1;
    // kin >> t;
    rep (t) solve();

    return 0;
}
// Author: kk2
// converted by https://github.com/kk2a/cpp-bundle
// 2025-03-31 07:57:46