// Powered by ACHelper (https://github.com/AlCash07/ACHelper)

#ifndef TEMPLATE_H
#define TEMPLATE_H

// #include <bits/stdc++.h>

#include <stdexcept>
#include <iostream>
#include <iomanip>
#include <fstream>
#include <sstream>
#include <cassert>
#include <cstdarg>
#include <cstring>
#include <cstdio>
#include <memory>
#include <random>
#include <cmath>
#include <ctime>
#include <unordered_map>
#include <unordered_set>
#include <functional>
#include <algorithm>
#include <complex>
#include <numeric>
#include <limits>
#include <bitset>
#include <vector>
#include <string>
#include <queue>
#include <deque>
#include <array>
#include <list>
#include <map>
#include <set>

using namespace std;

#define all(a) (a).begin(), (a).end()
#define sz(a) static_cast<int>((a).size())
#define FOR(i, a, b) for (int i(a), b_(b); i < b_; ++i)
#define REP(i, n) FOR (i, 0, n)
#define FORD(i, a, b) for (int i(a), b_(b); i >= b_; --i)
#define UNIQUE(a) sort(all(a)), (a).erase(unique(all(a)), (a).end())
#define CL(a, v) memset(a, v, sizeof a)
#define eb emplace_back
#define pb push_back
#define X first
#define Y second

typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef pair<int, int> pii;
template <class T> using min_queue = priority_queue<T, vector<T>, greater<T>>;

const int INF = static_cast<int>(1e9);
const long long INF_LL = static_cast<long long>(4e18);
const double pi = acos(-1.0);

#endif  // TEMPLATE_H





#include <utility>


namespace atl {

/***********************************************************************************************//**
 *  Read and write support for standard complex types:
 *  - pair
 *  - complex
 *  - vector (size and then the elements)
 **************************************************************************************************/

template <class Reader, class T1, class T2>
inline bool read(Reader& reader, std::pair<T1, T2>& arg) {
    return read(reader, arg.first, arg.second);
}

template <class Reader, class T>
inline bool read(Reader& reader, std::complex<T>& arg) {
    T real, imag;
    if (!read(reader, real, imag)) return false;
    arg.real(real);
    arg.imag(imag);
    return true;
}

template <class Reader, class T>
inline bool read(Reader& reader, std::vector<T>& arg) {
    uint32_t size;
    if (!read(reader, size)) return false;
    arg.resize(size);
    return read(reader, arg.begin(), arg.end());
}

template <class Writer, class T1, class T2>
inline int write(Writer& writer, const std::pair<T1, T2>& arg) {
    return write(writer, arg.first, arg.second);
}

template <class Writer, class T>
inline int write(Writer& writer, const std::complex<T>& arg) {
    return write(writer, real(arg), imag(arg));
}

template <class Writer, class T>
inline int write(Writer& writer, const std::vector<T>& arg) {
    return write(writer, static_cast<uint32_t>(arg.size()), arg.begin(), arg.end());
}

}  // namespace atl





#ifndef ATL_ASSERT
#ifdef AlCash

#include <stdexcept>
#include <string>

#define ATL_ASSERT(condition) \
    if(!(condition)) { \
        throw std::runtime_error(std::string() + #condition + \
            " in line " + std::to_string(__LINE__) + " in " + __PRETTY_FUNCTION__); \
    }

#else

#define ATL_ASSERT(condition) ((void)0)

#endif
#endif





#include <iterator>

namespace atl {

template <class Iterator> class range;

namespace detail {

template <class Iterator, class Category> class range_base;

template <class I>
class range_base<I, std::forward_iterator_tag> : public std::iterator_traits<I> {
public:
    using iterator  = I;
    using size_type = std::size_t;
    // all other type aliases come from std::iterator_traits<I>

    I begin() const { return begin_; }

    I end() const { return end_; }

    bool empty() const { return begin_ == end_; }

    bool operator () () const { return !empty(); }

    typename std::iterator_traits<I>::reference front() const {
        ATL_ASSERT(!empty());
        return *begin_;
    }

    void drop_front() {
        ATL_ASSERT(!empty());
        ++begin_;
    }

protected:
    range_base() : begin_(), end_() {}

    template <class I1>
    range_base(I1 begin, I1 end) : begin_(begin), end_(end) {}

    I begin_;
    I end_;
};

template <class I>
class range_base<I, std::input_iterator_tag> : public range_base<I, std::forward_iterator_tag> {
    using base_type = range_base<I, std::forward_iterator_tag>;
protected:
    range_base() : base_type() {}

    template <class I1>
    range_base(I1 first, I1 last) : base_type(first, last) {}
};

template <class I>
class range_base<I, std::output_iterator_tag> : public range_base<I, std::forward_iterator_tag> {
    using base_type = range_base<I, std::forward_iterator_tag>;
protected:
    range_base() : base_type() {}

    template <class I1>
    range_base(I1 first, I1 last) : base_type(first, last) {}
};

template <class I>
class range_base<I, std::bidirectional_iterator_tag>
    : public range_base<I, std::forward_iterator_tag> {
    using base_type = range_base<I, std::forward_iterator_tag>;
public:
    typename base_type::reference back() const {
        ATL_ASSERT(!this->empty());
        typename base_type::iterator end = this->end_;
        return *--end;
    }

    void drop_back() {
        ATL_ASSERT(!this->empty());
        --this->end_;
    }

protected:
    range_base() : base_type() {}

    template <class I1>
    range_base(I1 first, I1 last) : base_type(first, last) {}
};

template <class I>
class range_base<I, std::random_access_iterator_tag>
    : public range_base<I, std::bidirectional_iterator_tag> {
    using base_type = range_base<I, std::bidirectional_iterator_tag>;
public:
    typename base_type::reference operator [] (typename base_type::difference_type at) const {
        ATL_ASSERT(at >= 0);
        ATL_ASSERT(static_cast<typename base_type::size_type>(at) < size());
        return this->begin_[at];
    }

    typename base_type::size_type size() const { return this->end_ - this->begin_; }

protected:
    range_base() : base_type() {}

    template <class I1>
    range_base(I1 first, I1 last) : base_type(first, last) {}
};

}  // namespace detail

template <class I>
class range
    : public detail::range_base<I, typename std::iterator_traits<I>::iterator_category> {
    using base_type = detail::range_base<I, typename std::iterator_traits<I>::iterator_category>;
public:
    range() {}

    template <class Iterator>
    range(Iterator first, Iterator last) : base_type(first, last) {}
};

template <class Iterator>
inline range<Iterator> make_range(Iterator first, Iterator last) {
    return range<Iterator>(first, last);
}

template <class Iterator, class Integer>
inline range<Iterator> make_range(Iterator first, Integer n) {
    return range<Iterator>(first, std::next(first, n));
}

template <class Container>
inline range<typename Container::iterator> make_range(Container& container) {
    return make_range(container.begin(), container.end());
}

}  // namespace atl


#include <type_traits>

namespace atl {

template <class T>
struct is_iterator {
    template <class U>
    constexpr static auto has_indirection(int) -> decltype(*std::declval<U>(), bool()) {
        return true;
    }

    template <class>
    constexpr static bool has_indirection(long) { return false; }

    constexpr static bool value = has_indirection<T>(0);
};

namespace detail {

template <class T, bool IS_ITERATOR = false>
struct remove_iterator_impl {
    using type = T;
};

template <class T>
struct remove_iterator_impl<T, true> {
    using type = typename std::remove_reference<decltype(*std::declval<T>())>::type;
};

}  // namespace detail

template <class T>
struct remove_iterator {
    using type = typename detail::remove_iterator_impl<T, is_iterator<T>::value>::type;
};

template <class T>
struct is_const_iterator {
    constexpr static bool value = is_iterator<T>::value &&
        std::is_const<typename remove_iterator<T>::type>::value;
};

template <class T>
struct is_non_const_iterator {
    constexpr static bool value = is_iterator<T>::value && !is_const_iterator<T>::value;
};

}  // namespace atl


namespace atl {

/***********************************************************************************************//**
 *  Read returns true if all the arguments were successfully read.
 *  Arguments supported by default:
 *  - char, standard integer and floating point types
 *  - range
 *  Two consecutive arguments starting with an output iterator are treated as a range:
 *  - Iterator first, Iterator last
 *  - Iterator first, Integer count
 **************************************************************************************************/

template <class Reader>
inline bool read(Reader& reader) { return true; }

template <class Reader, class T1, class T2, class... Ts>
inline typename std::enable_if<is_non_const_iterator<T1>::value, bool>::type
read(Reader& reader, T1&& arg1, T2&& arg2, Ts&&... args) {
    return read(reader, make_range(std::forward<T1>(arg1), std::forward<T2>(arg2)),
        std::forward<Ts>(args)...);
}

template <class Reader, class T1, class T2, class... Ts>
inline typename std::enable_if<!is_non_const_iterator<T1>::value, bool>::type
read(Reader& reader, T1&& arg1, T2&& arg2, Ts&&... args) {
    return read(reader, std::forward<T1>(arg1)) &&
        read(reader, std::forward<T2>(arg2), std::forward<Ts>(args)...);
}

/***********************************************************************************************//**
 *  Write returns number of characters written. Parameters:
 *  Arguments supported by default:
 *  - char, standard integer and floating point types
 *  - string, const char*
 *  Two consecutive arguments starting with non-character iterator are treated as a range:
 *  - Iterator first, Iterator last
 *  - Iterator first, int count
 **************************************************************************************************/

template <class Writer>
inline int write(Writer& writer) { return 0; }

template <class T>
struct is_range_begin {
    constexpr static bool value = is_iterator<T>::value &&
        !std::is_convertible<T, const char*>::value;
};

template <class Writer, class T1, class T2, class... Ts>
inline typename std::enable_if<is_range_begin<T1>::value, int>::type
write(Writer& writer, T1&& arg1, T2&& arg2, Ts&&... args) {
    return write(writer, make_range(std::forward<T1>(arg1), std::forward<T2>(arg2)),
        std::forward<Ts>(args)...);
}

template <class Writer, class T1, class T2, class... Ts>
inline typename std::enable_if<!is_range_begin<T1>::value, int>::type
write(Writer& writer, T1&& arg1, T2&& arg2, Ts&&... args) {
    int charsWritten = write(writer, std::forward<T1>(arg1));
    return charsWritten + write(writer, std::forward<T2>(arg2), std::forward<Ts>(args)...);
}

template <class Writer, class... Ts>
int writeln(Writer& writer, Ts&&... args) {
    return write(writer, std::forward<Ts>(args)..., '\n');
}

}  // namespace atl



#include <cstdint>


namespace atl {

namespace detail {
struct Base { uint32_t value; };
}  // namespace detail

}  // namespace atl


namespace atl {

template <class T>
inline constexpr T& smin(T& x, const T& y) {
    return y < x ? x = y : x;
}

template <class T>
inline constexpr T& smax(T& x, const T& y) {
    return x < y ? x = y : x;
}

template <class T>
inline constexpr T abs(const T& x) {
    return x < T(0) ? -x : x;
}

template <class T>
inline constexpr int sgn(const T& x) {
    return (T(0) < x) - (x < T(0));
}

template <class T>
inline constexpr T sqr(const T& x) {
    return x * x;
}

}  // namespace atl


namespace atl {

static inline bool isSpace(char c) {
    return static_cast<unsigned char>(c - '\t') < 5 || c == ' ';
}

static inline bool isDigit(char c) { return static_cast<unsigned char>(c - '0') < 10; }

static inline bool isUpper(char c) { return static_cast<unsigned char>(c - 'A') < 26; }

static inline bool isLower(char c) { return static_cast<unsigned char>(c - 'a') < 26; }

}  // namespace atl




namespace atl {

/***********************************************************************************************//**
 *  TextReader extends read arguments with the following:
 *  - setBase(uint32_t): base for integer and floating point numbers
 *  Characters skip:
 *  - char: skip until the given character is encountered and read it
 *  - const char*: skip all the characters from the string
 *  - predicate: skip all the characters satisfying the predicate
 *  Character ranges are treated differently:
 *    they are read until the range size is reached or termination character is found
 *    (one of the characters in a given string or defined by predicate, isspace by default)
 *  - char (&)[N], terminator
 *  - range<char>, terminator
 *  - string&, terminator
 **************************************************************************************************/
class TextReader {
public:
    TextReader(TextReader const&) = delete;
    TextReader& operator = (TextReader const&) = delete;

    // can be called only once directly after successfully reading a character
    void putBack() { --head; }

    bool eof() {
        if (__builtin_expect(head < tail, true)) return true;
        fillBuffer();
        return head < tail;
    }

    // property setters
    friend inline bool read(TextReader& reader, detail::Base base) {
        reader.base = base.value;
        return true;
    }

    // primitive types
    friend inline bool read(TextReader& reader, char& arg) {
        if (reader.eof()) {
            arg = '\0';
            return false;
        } else {
            arg = *reader.head++;
            return true;
        }
    }

    template <class Uint>
    friend inline typename std::enable_if<std::is_integral<Uint>::value &&
        std::is_unsigned<Uint>::value, bool>::type
    read(TextReader& reader, Uint& arg) {
        return reader.readUnsignedInt(arg, reader.skipCharacters()) > 0;
    }

    template <class Int>
    friend inline typename std::enable_if<std::is_integral<Int>::value &&
        std::is_signed<Int>::value, bool>::type
    read(TextReader& reader, Int& arg) {
        char c = reader.skipCharacters();
        bool negative = c == '-';
        if (negative) c = reader.nextChar();
        typename std::make_unsigned<Int>::type unsignedArg;
        if (reader.readUnsignedInt(unsignedArg, c) == 0) return false;
        arg = negative ? ~static_cast<Int>(unsignedArg - 1) : static_cast<Int>(unsignedArg);
        return true;
    }

    template <class Float>
    friend inline typename std::enable_if<std::is_floating_point<Float>::value, bool>::type
    read(TextReader& reader, Float& arg) {
        char c = reader.skipCharacters();
        bool negative = c == '-';
        if (negative) c = reader.nextChar();
        unsigned long long integerPart;
        if (reader.readUnsignedInt(integerPart, c) == 0) return false;
        arg = static_cast<Float>(integerPart);
        if (reader.nextChar() == '.') {
            unsigned long long fractionalPart = 0;
            int fractionalLength = reader.readUnsignedInt(fractionalPart, reader.nextChar());
            if (fractionalLength > 0) {
                unsigned long long basePower = 1;
                for (; fractionalLength; --fractionalLength)
                    basePower *= reader.base;
                arg += static_cast<Float>(fractionalPart) / basePower;
            }
        } else {
            reader.putBack();
        }
        if (negative) arg = -arg;
        return true;
    }

    char skipCharacters() { return skipCharacters(isSpace); }

    char skipCharacters(const char* arg) {
        if (!*arg) return skipCharacters();
        return skipCharacters([this, arg](char c) { return isOneOf(c, arg); });
    }

    template <class UnaryPredicate>
    char skipCharacters(UnaryPredicate isSkipped) {
        char c;
        do { c = nextChar(); } while (isSkipped(c));
        return c;
    }

    int readString(char* arg, int limit, const char* terminators) {
        if (!*terminators) return readString(arg, limit, isSpace);
        return readString(arg, limit, [this, terminators](char c) {
            return isOneOf(c, terminators);
        });
    }

    template <class UnaryPredicate>
    int readString(char* arg, int limit, UnaryPredicate isTerminator) {
        int charsRead = 0;
        // reserve space for null character
        for (--limit; head < tail; fillBuffer()) {
            std::ptrdiff_t chunkSize =
                std::find_if(head, std::min(tail, head + limit - charsRead), isTerminator) - head;
            arg = std::copy_n(head, chunkSize, arg);
            head += chunkSize;
            charsRead += chunkSize;
            if (chunkSize == 0 || head < tail) break;
        }
        *arg = '\0';
        return charsRead;
    }

    uint32_t base;

protected:
    const char* head;
    const char* tail;

    TextReader(const char* head, const char* tail)
        : base(10)
        , head(head)
        , tail(tail)
    {}

    virtual void fillBuffer() = 0;

private:
    static inline bool isOneOf(char c, const char* str) { return std::strchr(str, c) != nullptr; }

    inline char nextChar() {
        if (__builtin_expect(head >= tail, false)) fillBuffer();
        return *head++;
    }

    template <class I>
    int readUnsignedIntGeneral(I& arg, char c) {
        I value = 0;
        int length = 0;
        for (;; c = nextChar()) {
            if (isDigit(c)) c -= '0';
            else if (isUpper(c)) c -= 'A' - 10;
            else if (isLower(c)) c -= 'a' - 10;
            else c = static_cast<char>(base);
            if (c >= base) break;
            value = base * value + c;
            ++length;
        }
        putBack();
        arg = value;
        return length;
    }

    template <class I>
    inline int readUnsignedInt(I& arg, char c) {
        if (__builtin_expect(base > 10, false)) return readUnsignedIntGeneral(arg, c);
        I value = 0;
        int length = 0;
        for (; static_cast<unsigned char>(c - '0') < base; c = nextChar()) {
            value = base * value + c - '0';
            ++length;
        }
        putBack();
        arg = value;
        return length;
    }
};

// characters skip
inline bool read(TextReader& reader, const char& arg) {
    reader.skipCharacters([arg](char c) { return arg != c; });
    reader.putBack();
    return true;
}

inline bool read(TextReader& reader, const char* arg) {
    reader.skipCharacters(arg);
    reader.putBack();
    return true;
}

inline bool read(TextReader& reader, bool (*isSkipped)(char)) {
    reader.skipCharacters(isSkipped);
    reader.putBack();
    return true;
}

// ranges
template <bool STRING> struct rangeReader;

template <>
struct rangeReader<false> {
    template <class T, class... Ts>
    static bool f(TextReader& reader, const range<T>& arg, Ts&&... args) {
        for (auto& i : arg) {
            if (!read(reader, i)) return false;
        }
        return read(reader, std::forward<Ts>(args)...);
    }
};

template <>
struct rangeReader<true> {
    template <class Terminator, class... Ts>
    static bool f(TextReader& reader, const range<char*>& arg, Terminator terminator,
        Ts&&... args) {
        reader.skipCharacters(terminator);
        reader.putBack();
        reader.readString(arg.begin(), arg.size(), terminator);
        return atl::read(reader, std::forward<Ts>(args)...);
    }

    static bool f(TextReader& reader, const range<char*>& arg) { return f(reader, arg, ""); }
};

template <class T, class... Ts>
inline bool read(TextReader& reader, const range<T>& range, Ts&&... args) {
    return rangeReader<std::is_same<T, char*>::value>::f(reader, range, std::forward<Ts>(args)...);
};

template <int N, class... Ts>
inline bool read(TextReader& reader, char (&arg)[N], Ts&&... args) {
    return read(reader, make_range(static_cast<char*>(arg), N), std::forward<Ts>(args)...);
}

// std::string
template <class Terminator, class... Ts>
inline bool read(TextReader& reader, std::string& arg, Terminator terminator, Ts&&... args) {
    reader.skipCharacters(terminator);
    reader.putBack();
    uint32_t length = std::max(16u, static_cast<uint32_t>(arg.capacity()));
    for (uint32_t last = 0;; length = last += length) {
        arg.resize(last + length);
        int charsRead = reader.readString(&arg[last], length + 1, terminator);
        if (charsRead < length) {
            arg.resize(last + charsRead);
            return read(reader, std::forward<Ts>(args)...);
        }
    }
}

inline bool read(TextReader& reader, std::string& arg) { return read(reader, arg, ""); }

}  // namespace atl




namespace atl {

// text file reader
class FileReader final : public TextReader {
public:
    FileReader(std::FILE* file = stdin, bool lineBuffered = true, bool takeOwnership = false)
        : TextReader(buffer, buffer)
        , file(file)
        , lineBuffered(lineBuffered)
        , owner(takeOwnership)
    {}

    FileReader(const char* fileName) : FileReader(std::fopen(fileName, "r"), false, true) {}

    ~FileReader() {
        if (owner) std::fclose(file);
    }

private:
    static const uint32_t BUFFER_SIZE = 1 << 12;

    void fillBuffer() override {
        head = buffer;
        *buffer = '\0';
        if (__builtin_expect(!lineBuffered, true)) {
            tail = head + std::fread(buffer, 1, BUFFER_SIZE, file);
        } else {
            tail = head;
            if (std::fgets(buffer, BUFFER_SIZE, file)) {
                while (*tail) ++tail;
            }
        }
    }

    std::FILE* file;
    bool lineBuffered;
    bool owner;
    char buffer[BUFFER_SIZE];
};

}  // namespace atl







namespace atl {

// Maximum possible length of a string representing primitive type
// assuming we won't encounter huge double values.
static const uint32_t MAX_LENGTH = 1 << 7;

namespace detail {

struct Width { uint32_t value; };
struct Fill { char value; };
struct Precision { uint32_t value; };
struct Delimiter { const char* value; };

}  // namespace detail

/***********************************************************************************************//**
 *  TextWriter extends write arguments with the following:
 *  - setWidth(uint32_t): minimum width of a single element to write (except char)
 *  - setFill(char): character prepended to an element until set width is reached
 *  - setBase(uint32_t): base for integer and floating point numbers
 *  - setPrecision(uint32_t): number of digits after the decimal point
 *  - setDelimiter(const char*): delimiter automatically inserted between elements
 *    that are not strings or characters
 *  Strings are written until the null character is reached
 **************************************************************************************************/
class TextWriter {
public:
    TextWriter(TextWriter const&) = delete;
    TextWriter& operator = (TextWriter const&) = delete;

    virtual ~TextWriter() {}

    void flush() {
        flushBuffer(static_cast<uint32_t>(output - buffer));
        output = buffer;
    }

    // property setters
    friend inline int write(TextWriter& writer, detail::Width width) {
        writer.width = width.value;
        return 0;
    }

    friend inline int write(TextWriter& writer, detail::Fill fill) {
        writer.fill = fill.value;
        return 0;
    }

    friend inline int write(TextWriter& writer, detail::Base base) {
        writer.base = base.value;
        writer.computeBasePower();
        return 0;
    }

    friend inline int write(TextWriter& writer, detail::Precision precision) {
        writer.precision = precision.value;
        writer.computeBasePower();
        return 0;
    }

    friend inline int write(TextWriter& writer, detail::Delimiter delimiter) {
        writer.delimiter = delimiter.value;
        return 0;
    }

    // primitive types
    friend inline int write(TextWriter& writer, char arg) {
        writer.separate = false;
        *writer.output++ = arg;
        writer.flushMaybe();
        return 1;
    }

    template <class Int>
    friend inline typename std::enable_if<std::is_integral<Int>::value &&
        std::is_unsigned<Int>::value, int>::type
    write(TextWriter& writer, Int arg) {
        return writer.writeT(writer.writeUnsignedInt(arg, writer.end));
    }

    template <class Int>
    friend inline typename std::enable_if<std::is_integral<Int>::value &&
        std::is_signed<Int>::value, int>::type
    write(TextWriter& writer, Int arg) {
        return writer.writeT(writer.writeSignedInt(arg, writer.end));
    }

    template <class Float>
    friend inline typename std::enable_if<std::is_floating_point<Float>::value, int>::type
    write(TextWriter& writer, Float arg) {
        return writer.writeT(writer.writeFloatingPoint(arg, writer.end));
    }

    // ranges
    friend inline int write(TextWriter& writer, const char* arg) {
        return writer.writeString(arg, std::strlen(arg));
    }

    template <int N>
    friend inline int write(TextWriter& writer, char (&arg)[N]) {
        return writer.writeString(arg, std::strlen(arg));
    }

    friend inline int write(TextWriter& writer, const std::string& arg) {
        return writer.writeString(arg.data(), arg.size());
    }

    template <class T, class... Ts>
    friend int write(TextWriter& writer, const range<T>& arg, Ts&&... args) {
        int charsWritten = 0;
        bool isFirst = true;
        for (const auto& i : arg) {
            if (!isFirst) {
                charsWritten += writer.writeDelimiter();
            }
            isFirst = false;
            charsWritten += write(writer, i);
        }
        return charsWritten + write(writer, std::forward<Ts>(args)...);
    }

    uint32_t width;
    char fill;
    uint32_t base;
    uint32_t precision;
    unsigned long long basePower;
    std::string delimiter;

protected:
    static const uint32_t BUFFER_SIZE = 1 << 12;

    char buffer[BUFFER_SIZE + MAX_LENGTH];
    char* output;
    char* end;
    bool separate;

    TextWriter()
        : width(0)
        , fill(' ')
        , base(10)
        , precision(9)
        , delimiter(" ")
        , output(buffer)
        , end(buffer + BUFFER_SIZE + MAX_LENGTH)
        , separate(false)
    { computeBasePower(); }

    virtual void flushBuffer(uint32_t count) = 0;

private:
    void flushMaybe() {
        if (__builtin_expect(output >= buffer + BUFFER_SIZE, false)) {
            flushBuffer(BUFFER_SIZE);
            output = std::copy(buffer + BUFFER_SIZE, output, buffer);
        }
    }

    void computeBasePower() {
        basePower = 1;
        for (uint32_t i = 0; i < precision; ++i) basePower *= base;
    }

    template <class I>
    inline char* writeUnsignedInt(I arg, char* last) {
        if (__builtin_expect(arg == 0, false)) *--last = '0';
        if (__builtin_expect(base == 10, true)) {
            for (; arg; arg /= 10) *--last = '0' + arg % 10;
        } else {
            for (; arg; arg /= base) {
                I digit = arg % base;
                *--last = digit < 10 ? '0' + digit : 'A' - 10 + digit;
            }
        }
        return last;
    }

    template <class I>
    inline char* writeSignedInt(I arg, char* last) {
        auto unsignedArg = static_cast<typename std::make_unsigned<I>::type>(arg);
        if (arg < 0) {
            last = writeUnsignedInt(~unsignedArg + 1, last);
            *--last = '-';
            return last;
        }
        return writeUnsignedInt(unsignedArg, last);
    }

    template <class F>
    char* writeFloatingPoint(F arg, char* last) {
        bool negative = std::signbit(arg);
        if (negative) arg = -arg;
        if (std::isnan(arg)) {
            for (int i = 0; i < 3; ++i)
                *--last = "NaN"[i];
        } else if (std::isinf(arg)) {
            for (int i = 0; i < 3; ++i)
                *--last = "fnI"[i];
        } else {
            auto integerPart = static_cast<unsigned long long>(arg);
            auto fractionalPart =
                static_cast<unsigned long long>((arg - integerPart) * basePower + F(1) / 2);
            if (fractionalPart >= basePower) {
                ++integerPart;
                fractionalPart = 0;
            }
            char* point = last - precision;
            if (precision > 0) {
                std::fill(point, writeUnsignedInt(fractionalPart, last), '0');
                *--point = '.';
            }
            last = writeUnsignedInt(integerPart, point);
        }
        if (negative) *--last = '-';
        return last;
    }

    inline int writeT(char* first) {
        int delimiterLength = separate ? writeDelimiter() : 0;
        separate = true;
        uint32_t charsWritten = static_cast<uint32_t>(end - first);
        if (__builtin_expect(charsWritten < width, false))
            charsWritten += writeFill(width - charsWritten);
        output = std::copy(first, end, output);
        flushMaybe();
        return delimiterLength + static_cast<int>(charsWritten);
    }

    inline int writeFill(uint32_t count) {
        int charsWritten = static_cast<int>(count);
        if (__builtin_expect(output + count + MAX_LENGTH < end, true)) {
            if (count == 1) *output++ = fill;
            else output = std::fill_n(output, count, fill);
        } else {
            uint32_t chunkSize = static_cast<uint32_t>(buffer + BUFFER_SIZE - output);
            for (;; chunkSize = BUFFER_SIZE) {
                if (chunkSize > count) chunkSize = count;
                output = std::fill_n(output, chunkSize, fill);
                flushMaybe();
                if ((count -= chunkSize) == 0) break;
            }
        }
        return charsWritten;
    }

    inline int writeString(const char* arg, size_t length, bool checkWidth = true) {
        separate = false;
        uint32_t count = static_cast<uint32_t>(length);
        int charsWritten = static_cast<int>(count);
        if (checkWidth && count < width)
            charsWritten += writeFill(width - count);
        if (__builtin_expect(output + count + MAX_LENGTH < end, true)) {
            if (count == 1) {
                *output++ = *arg;
            } else {
                output = std::copy_n(arg, count, output);
            }
        } else {
            uint32_t chunkSize = static_cast<uint32_t>(buffer + BUFFER_SIZE - output);
            for (;; chunkSize = BUFFER_SIZE) {
                if (chunkSize > count) chunkSize = count;
                output = std::copy_n(arg, chunkSize, output);
                flushMaybe();
                if ((count -= chunkSize) == 0) break;
                arg += chunkSize;
            }
        }
        return charsWritten;
    }

    int writeDelimiter() { return writeString(delimiter.c_str(), delimiter.size(), false); }
};

}  // namespace atl




namespace atl {

class FileWriter final : public TextWriter {
public:
    FileWriter(FILE* file = stdout, bool takeOwnership = false)
        : file(file)
        , owner(takeOwnership)
    {}

    FileWriter(const char* fileName) : FileWriter(std::fopen(fileName, "w"), true) {}

    ~FileWriter() override {
        flush();
        if (owner) std::fclose(file);
    }

private:
    void flushBuffer(uint32_t count) override {
        std::fwrite(buffer, 1, count, file);
        std::fflush(file);
    }

    std::FILE* file;
    bool owner;
};

}  // namespace atl


using namespace std;
using namespace atl;

void solve(FileReader& in, FileWriter& out);







namespace atl {

template <class Derived, class Category, class Value, class Reference = Value&,
    class Pointer = Value*, class Distance = std::ptrdiff_t>
class iterator_facade;

struct iterator_core_access {
    template <class I>
    static typename I::reference dereference(const I& i) { return i.dereference(); }

    template <class I>
    static void increment(I& i) { i.increment(); }

    template <class I>
    static void decrement(I& i) { i.decrement(); }

    template <class I1, class I2>
    static bool equal(const I1& i1, const I2& i2) { return i1.equals(i2); }
};

namespace detail {

template <class Iterator, class Category, class Value, class Reference,
    class Pointer, class Distance>
class iterator_facade_base;

template <class I, class V, class R, class P, class D>
class iterator_facade_base<I, std::output_iterator_tag, V, R, P, D>
    : public std::iterator<std::output_iterator_tag, V, D, P, R> {
public:
    R operator * () const { return iterator_core_access::dereference(derived()); }

    I& operator ++ () {
        iterator_core_access::increment(derived());
        return derived();
    }

    I operator ++ (int) {
        I copy = derived();
        ++*this;
        return copy;
    }

protected:
    I& derived() { return *static_cast<I*>(this); }

    const I& derived() const { return *static_cast<const I*>(this); }
};

template <class I, class V, class R, class P, class D>
class iterator_facade_base<I, std::input_iterator_tag, V, R, P, D>
    : public iterator_facade_base<I, std::output_iterator_tag, V, R, P, D> {
public:
    using iterator_category = std::input_iterator_tag;

    P operator -> () const { return *iterator_core_access::dereference(this->derived()); }
};

template <class I, class V, class R, class P, class D>
class iterator_facade_base<I, std::forward_iterator_tag, V, R, P, D>
    : public iterator_facade_base<I, std::input_iterator_tag, V, R, P, D> {
public:
    using iterator_category = std::forward_iterator_tag;
};

template <class I, class V, class R, class P, class D>
class iterator_facade_base<I, std::bidirectional_iterator_tag, V, R, P, D>
    : public iterator_facade_base<I, std::forward_iterator_tag, V, R, P, D> {
public:
    using iterator_category = std::bidirectional_iterator_tag;

    I& operator -- () {
        iterator_core_access::decrement(this->derived());
        return this->derived();
    }

    I operator -- (int) {
        I copy = this->derived();
        --*this;
        return copy;
    }
};

}  // namespace detail

template <class I, class C, class V, class R, class P, class D>
class iterator_facade : public detail::iterator_facade_base<I, C, V, R, P, D> {};

template <class I, class C, class V, class R, class P, class D>
inline bool operator == (const iterator_facade<I, C, V, R, P, D>& lhs,
    const iterator_facade<I, C, V, R, P, D>& rhs) {
    return iterator_core_access::equal(*static_cast<const I*>(&lhs), *static_cast<const I*>(&rhs));
};

template <class I, class C, class V, class R, class P, class D>
inline bool operator != (const iterator_facade<I, C, V, R, P, D>& lhs,
    const iterator_facade<I, C, V, R, P, D>& rhs) {
    return !(lhs == rhs);
}

}  // namespace atl




namespace atl {

template <typename Integer, bool INCREMENT = true>
class integer_iterator : public iterator_facade<integer_iterator<Integer, INCREMENT>,
    std::input_iterator_tag, Integer, const Integer, Integer*, Integer> {
public:
    explicit integer_iterator() : value_() {}

    explicit integer_iterator(Integer value) : value_(value) {}

private:
    friend struct iterator_core_access;

    const Integer dereference() const { return value_; }

    void increment() { INCREMENT ? ++value_ : --value_; }

    bool equals(const integer_iterator& other) const { return value_ == other.value_; }

    Integer value_;
};

template <typename Integer>
class integer_iterator_with_step : public iterator_facade<integer_iterator_with_step<Integer>,
    std::input_iterator_tag, Integer, const Integer, Integer*, Integer> {
public:
    explicit integer_iterator_with_step() : value_(), step_(1) {}

    explicit integer_iterator_with_step(Integer value, Integer step) : value_(value), step_(step) {}

private:
    friend struct iterator_core_access;

    const Integer dereference() const { return value_; }

    void increment() { value_ += step_; }

    bool equals(const integer_iterator_with_step& other) const { return value_ == other.value_; }

    Integer value_;
    Integer step_;
};

}  // namespace atl



namespace atl {

template <class Integer>
inline range<integer_iterator<Integer>> irange(Integer first, Integer last) {
    auto begin = integer_iterator<Integer>(first);
    if (first > last) return make_range(begin, begin);
    return make_range(begin, integer_iterator<Integer>(last));
}

template <class Integer>
inline range<integer_iterator<Integer>> irange(Integer last) { return irange(Integer(), last); }

template <class Integer>
inline range<integer_iterator<Integer, false>> drange(Integer first, Integer last) {
    auto begin = integer_iterator<Integer, false>(first);
    if (first < last) return make_range(begin, begin);
    return make_range(begin, integer_iterator<Integer, false>(last - 1));
}

template <class Integer>
inline range<integer_iterator<Integer, false>> drange(Integer first) {
    return drange(first, Integer());
}

template <typename Integer, typename StepType>
inline range<integer_iterator_with_step<Integer>>
irange(Integer first, Integer last, StepType step) {
    ATL_ASSERT(step != 0);
    auto begin = integer_iterator_with_step<Integer>(first, step);
    if (step > 0 ? (last < first) : (last > first)) return make_range(begin, begin);
    Integer stepCount = (last - first - (step > 0)) / step + 1;
    return make_range(begin, integer_iterator_with_step<Integer>(first + step * stepCount, step));
}

}  // namespace atl


class Solver {
public:
    static const int N = 2002;
    char s[N][N];
    int sum[N][N];
    int sumh[N][N];
    int sumv[N][N];

    void calc(int f[N][N], int n, int m) {
        for (int i : irange(n)) {
            for (int j : irange(m)) {
                f[i + 1][j + 1] += f[i + 1][j] + f[i][j + 1] - f[i][j];
            }
        }
    }

    int rect(int f[N][N], int x1, int y1, int x2, int y2) {
        return f[x1][y1] + f[x2][y2] - f[x1][y2] - f[x2][y1];
    }

    void solve(FileReader& in, FileWriter& out) {
        int n, m, q;
        read(in, n, m, q, s, n);
        REP(i, n) REP(j, m) {
                sum[i + 1][j + 1] = s[i][j] == '1';
            }
        calc(sum, n, m);
        REP(i, n - 1) REP(j, m) {
                sumv[i + 1][j + 1] = s[i][j] == '1' && s[i + 1][j] == '1';
            }
        calc(sumv, n - 1, m);
        REP(i, n) REP(j, m - 1) {
                sumh[i + 1][j + 1] = s[i][j] == '1' && s[i][j + 1] == '1';
            }
        calc(sumh, n, m - 1);
        REP(i, q) {
            int x1, y1, x2, y2;
            read(in, x1, y1, x2, y2);
            --x1;
            --y1;
            int ans = rect(sum, x1, y1, x2, y2);
            ans -= rect(sumv, x1, y1, x2 - 1, y2);
            ans -= rect(sumh, x1, y1, x2, y2 - 1);
            writeln(out, ans);
        }
    }
};

void solve(FileReader& in, FileWriter& out) {
    Solver solver;
    solver.solve(in, out);
}



int main() {
    const char* inputFileName = "";
    const char* outputFileName = "";

    unique_ptr<FileReader> in;
    if (*inputFileName) {
        in.reset(new FileReader(inputFileName));
    } else {
        in.reset(new FileReader(stdin, false));
    };

    unique_ptr<FileWriter> out;
    if (*outputFileName) {
        out.reset(new FileWriter(outputFileName));
    } else {
        out.reset(new FileWriter(stdout));
    }

    solve(*in, *out);
    return 0;
}



Measured memory_bytes: 52736