#region いつもの
using System;
using System.Collections.Generic;
using System.Linq;
using AtCoderProject;
using AtCoderProject.Reader;
using IEnumerable = System.Collections.IEnumerable;
using IEnumerator = System.Collections.IEnumerator;
using BigInteger = System.Numerics.BigInteger;
using StringBuilder = System.Text.StringBuilder;
using static AtCoderProject.Global;
using static AtCoderProject.NumGlobal;

namespace AtCoderProject
{
    public static class Global
    {
        public static void Swap<T>(ref T a, ref T b) { T tmp = a; a = b; b = tmp; }
        public static T[] NewArray<T>(int len0, T value) => new T[len0].Fill(value);
        public static T[] NewArray<T>(int len0, Func<T> factory)
        {
            var arr = new T[len0];
            for (int i = 0; i < arr.Length; i++) arr[i] = factory();
            return arr;
        }
        public static T[][] NewArray<T>(int len0, int len1, T value) where T : struct
        {
            var arr = new T[len0][];
            for (int i = 0; i < arr.Length; i++) arr[i] = NewArray(len1, value);
            return arr;
        }
        public static T[][] NewArray<T>(int len0, int len1, Func<T> factory)
        {
            var arr = new T[len0][];
            for (int i = 0; i < arr.Length; i++) arr[i] = NewArray(len1, factory);
            return arr;
        }
        public static T[][][] NewArray<T>(int len0, int len1, int len2, T value) where T : struct
        {
            var arr = new T[len0][][];
            for (int i = 0; i < arr.Length; i++) arr[i] = NewArray(len1, len2, value);
            return arr;
        }
        public static T[][][] NewArray<T>(int len0, int len1, int len2, Func<T> factory)
        {
            var arr = new T[len0][][];
            for (int i = 0; i < arr.Length; i++) arr[i] = NewArray(len1, len2, factory);
            return arr;
        }
        public static T[][][][] NewArray<T>(int len0, int len1, int len2, int len3, T value) where T : struct
        {
            var arr = new T[len0][][][];
            for (int i = 0; i < arr.Length; i++) arr[i] = NewArray(len1, len2, len3, value);
            return arr;
        }
        public static T[][][][] NewArray<T>(int len0, int len1, int len2, int len3, Func<T> factory)
        {
            var arr = new T[len0][][][];
            for (int i = 0; i < arr.Length; i++) arr[i] = NewArray(len1, len2, len3, factory);
            return arr;
        }
        public static string AllLines<T>(IEnumerable<T> source) => string.Join("\n", source);
        public static string AllJoin<T>(IEnumerable<T> source) => string.Join(" ", source);
        public static string AllGrid<T>(IEnumerable<IEnumerable<T>> source) => AllLines(source.Select(AllJoin));
        public static bool UpdateMax(ref int r, int val) { if (r < val) { r = val; return true; } return false; }
        public static bool UpdateMax(ref long r, long val) { if (r < val) { r = val; return true; } return false; }
        public static bool UpdateMin(ref int r, int val) { if (r > val) { r = val; return true; } return false; }
        public static bool UpdateMin(ref long r, long val) { if (r > val) { r = val; return true; } return false; }
    }
    public static class NumGlobal
    {
        public static int Pow(int x, int y)
        {
            int res = 1;
            for (; y > 0; y >>= 1)
            {
                if ((y & 1) == 1) res *= x;
                x *= x;
            }
            return res;
        }
        public static BigInteger ParseBigInteger(string s)
        {
            /* 自前実装の方が速い */
            var res = BigInteger.Zero;
            var splited = new string[(s.Length + 7) / 8];
            for (var i = 0; i < splited.Length - 1; i++)
            {
                splited[i] = s.Substring(8 * i, 8);
            }
            splited[splited.Length - 1] = s.Substring(8 * (splited.Length - 1));
            foreach (var sp in splited)
            {
                res *= (int)Math.Pow(10, sp.Length);
                res += int.Parse(sp);
            }
            return res;
        }
        public static int BitCount(int x) { x -= (x >> 1) & 0x55555555; x = (x & 0x33333333) + ((x >> 2) & 0x33333333); x = (x + (x >> 4)) & 0x0f0f0f0f; x += x >> 8; x += x >> 16; return x & 0x3f; }
        public static int BitCount(long x) { x -= (x >> 1) & 0x5555555555555555; x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333); x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f; x += x >> 8; x += x >> 16; x += x >> 32; return (int)(x & 0x0000007f); }
        public static int MSB(int x) { x |= x >> 1; x |= x >> 2; x |= x >> 4; x |= x >> 8; x |= x >> 16; return BitCount(x) - 1; }
        public static int MSB(long x) { x |= x >> 1; x |= x >> 2; x |= x >> 4; x |= x >> 8; x |= x >> 16; x |= x >> 32; return BitCount(x) - 1; }
        public static int LSB(int x) { x |= x << 1; x |= x << 2; x |= x << 4; x |= x << 8; x |= x << 16; return 32 - BitCount(x); }
        public static int LSB(long x) { x |= x << 1; x |= x << 2; x |= x << 4; x |= x << 8; x |= x << 16; x |= x << 32; return 64 - BitCount(x); }
    }
    public static class Ext
    {
        public static long ToLong(this int i) => i;
        public static T[] Fill<T>(this T[] arr, T value)
        {
            for (var i = 0; i < arr.Length; i++) arr[i] = value;
            return arr;
        }
        public static T[] Sort<T>(this T[] arr) { Array.Sort(arr); return arr; }
        public static string[] Sort(this string[] arr) => Sort(arr, StringComparer.OrdinalIgnoreCase);
        public static T[] Sort<T, U>(this T[] arr, Func<T, U> selector) where U : IComparable<U> => Sort(arr, (a, b) => selector(a).CompareTo(selector(b)));
        public static T[] Sort<T>(this T[] arr, Comparison<T> comparison) { Array.Sort(arr, comparison); return arr; }
        public static T[] Sort<T>(this T[] arr, IComparer<T> comparer) { Array.Sort(arr, comparer); return arr; }
        public static T[] Reverse<T>(this T[] arr) { Array.Reverse(arr); return arr; }
        public static Tuple<int, T> MaxBy<T>(this T[] arr) where T : IComparable<T>
        {
            T max = arr[0];
            int maxIndex = 0;
            for (int i = 0; i < arr.Length; i++)
            {
                if (max.CompareTo(arr[i]) < 0)
                {
                    max = arr[i];
                    maxIndex = i;
                }
            }
            return Tuple.Create(maxIndex, max);
        }
        public static Tuple<TSource, TMax> MaxBy<TSource, TMax>
            (this IEnumerable<TSource> source, Func<TSource, TMax> maxBySelector)
            where TMax : IComparable<TMax>
        {
            TMax max;
            TSource maxByItem;

            var e = source.GetEnumerator();
            e.MoveNext();
            maxByItem = e.Current;
            max = maxBySelector(maxByItem);
            while (e.MoveNext())
            {
                var item = e.Current;
                var next = maxBySelector(item);
                if (max.CompareTo(next) < 0)
                {
                    max = next;
                    maxByItem = item;
                }
            }
            return Tuple.Create(maxByItem, max);
        }
        public static Tuple<int, T> MinBy<T>(this T[] arr) where T : IComparable<T>
        {
            T min = arr[0];
            int minIndex = 0;
            for (int i = 0; i < arr.Length; i++)
            {
                if (min.CompareTo(arr[i]) > 0)
                {
                    min = arr[i];
                    minIndex = i;
                }
            }
            return Tuple.Create(minIndex, min);
        }
        public static Tuple<TSource, TMin> MinBy<TSource, TMin>
            (this IEnumerable<TSource> source, Func<TSource, TMin> minBySelector)
            where TMin : IComparable<TMin>
        {
            TMin min;
            TSource minByItem;

            var e = source.GetEnumerator();
            e.MoveNext();
            minByItem = e.Current;
            min = minBySelector(minByItem);
            while (e.MoveNext())
            {
                var item = e.Current;
                var next = minBySelector(item);
                if (min.CompareTo(next) > 0)
                {
                    min = next;
                    minByItem = item;
                }
            }
            return Tuple.Create(minByItem, min);
        }
        public static IEnumerable<TSource> Append<TSource>(this IEnumerable<TSource> source, TSource element)
        {
            foreach (var item in source)
                yield return item;
            yield return element;
        }
        public static IEnumerable<TSource> Prepend<TSource>(this IEnumerable<TSource> source, TSource element)
        {
            yield return element;
            foreach (var item in source)
                yield return item;
        }
        public static IComparer<T> Reverse<T>(this IComparer<T> comparer) => Comparer<T>.Create((x, y) => comparer.Compare(y, x));
        public static Dictionary<TKey, int> GroupCount<TSource, TKey>(this IEnumerable<TSource> source, Func<TSource, TKey> keySelector) => source.GroupBy(keySelector).ToDictionary(g => g.Key, g => g.Count());
        public static Dictionary<TKey, int> GroupCount<TKey>(this IEnumerable<TKey> source) => source.GroupCount(i => i);
        public static TValue Get<TKey, TValue>(this Dictionary<TKey, TValue> dic, TKey key)
        {
            TValue v;
            dic.TryGetValue(key, out v);
            return v;
        }
        public static TValue GetOrInit<TKey, TValue>(this Dictionary<TKey, TValue> dic, TKey key, TValue value)
        {
            TValue v;
            if (dic.TryGetValue(key, out v))
                return v;
            return dic[key] = value;
        }
    }
    public class ReverseComparer<T> : Comparer<T> where T : IComparable<T>
    {
        private static ReverseComparer<T> defaultComparer;
        public static new IComparer<T> Default => defaultComparer ?? (defaultComparer = new ReverseComparer<T>());
        public override int Compare(T y, T x) => x.CompareTo(y);
        public override bool Equals(object obj) => obj != null && GetType() == obj.GetType();
        public override int GetHashCode() => GetType().GetHashCode();
    }
    public class ΔDebugView<T> { private IEnumerable<T> collection; public ΔDebugView(IEnumerable<T> collection) { if (collection == null) throw new ArgumentNullException(nameof(collection)); this.collection = collection; }[System.Diagnostics.DebuggerBrowsable(System.Diagnostics.DebuggerBrowsableState.RootHidden)] public T[] Items => collection.ToArray(); }
}
namespace AtCoderProject.Reader
{
    using System.IO;
    using System.Text;
    using System.Diagnostics;
    using System.Runtime.CompilerServices;
    [DebuggerStepThrough]
    public class ConsoleReader
    {
        const int BufSize = 1 << 12;
        private readonly byte[] buffer = new byte[BufSize];
        private readonly Stream input;
        private readonly Encoding encoding;
        private int pos = 0;
        private int len = 0;
        public ConsoleReader(Stream input, Encoding encoding) { this.input = input; this.encoding = encoding; }
        public ConsoleReader(Stream input) : this(input, Encoding.UTF8) { }
        public ConsoleReader(string text) : this(new MemoryStream(Encoding.UTF8.GetBytes(text))) { }
        private void MoveNext() { if (++pos >= len) { len = input.Read(buffer, 0, buffer.Length); if (len == 0) { buffer[0] = 10; } pos = 0; } }

        public int Int
        {
            [MethodImpl(MethodImplOptions.AggressiveInlining)]
            get
            {
                int res = 0;
                bool neg = false;
                while (buffer[pos] < 48) { neg = buffer[pos] == 45; MoveNext(); }
                do { res = checked(res * 10 + (buffer[pos] ^ 48)); MoveNext(); } while (48 <= buffer[pos]);
                return neg ? -res : res;
            }
        }
        public int Int0 => this.Int - 1;
        public long Long
        {
            [MethodImpl(MethodImplOptions.AggressiveInlining)]
            get
            {
                long res = 0;
                bool neg = false;
                while (buffer[pos] < 48) { neg = buffer[pos] == 45; MoveNext(); }
                do { res = res * 10 + (buffer[pos] ^ 48); MoveNext(); } while (48 <= buffer[pos]);
                return neg ? -res : res;
            }
        }
        public long Long0 => this.Long - 1;
        public string String
        {
            [MethodImpl(MethodImplOptions.AggressiveInlining)]
            get
            {
                var sb = new List<byte>();
                while (buffer[pos] <= 32) MoveNext();
                do { sb.Add(buffer[pos]); MoveNext(); } while (32 < buffer[pos]);
                return this.encoding.GetString(sb.ToArray());
            }
        }
        public string Ascii
        {
            [MethodImpl(MethodImplOptions.AggressiveInlining)]
            get
            {
                var sb = new StringBuilder();
                while (buffer[pos] <= 32) MoveNext();
                do { sb.Append((char)buffer[pos]); MoveNext(); } while (32 < buffer[pos]);
                return sb.ToString();
            }
        }
        public string Line
        {
            [MethodImpl(MethodImplOptions.AggressiveInlining)]
            get
            {
                var sb = new List<byte>();
                while (buffer[pos] < 32) MoveNext();
                do { sb.Add(buffer[pos]); MoveNext(); } while (buffer[pos] != 10 && buffer[pos] != 13);
                return this.encoding.GetString(sb.ToArray());
            }
        }
        public double Double => double.Parse(this.Ascii);

        [DebuggerStepThrough]
        public struct RepeatReader
        {
            ConsoleReader cr;
            int count;
            public RepeatReader(ConsoleReader cr, int count) { this.cr = cr; this.count = count; }
            public T[] Select<T>(Func<ConsoleReader, T> factory) { var arr = new T[count]; for (var i = 0; i < count; i++) arr[i] = factory(cr); return arr; }
            public string[] Line { get { var arr = new string[count]; for (var i = 0; i < count; i++) arr[i] = cr.Line; return arr; } }
            public string[] String { get { var arr = new string[count]; for (var i = 0; i < count; i++) arr[i] = cr.String; return arr; } }
            public string[] Ascii { get { var arr = new string[count]; for (var i = 0; i < count; i++) arr[i] = cr.Ascii; return arr; } }
            public int[] Int { get { var arr = new int[count]; for (var i = 0; i < count; i++) arr[i] = cr.Int; return arr; } }
            public int[] Int0 { get { var arr = new int[count]; for (var i = 0; i < count; i++) arr[i] = cr.Int0; return arr; } }
            public long[] Long { get { var arr = new long[count]; for (var i = 0; i < count; i++) arr[i] = cr.Long; return arr; } }
            public long[] Long0 { get { var arr = new long[count]; for (var i = 0; i < count; i++) arr[i] = cr.Long0; return arr; } }
            public double[] Double { get { var arr = new double[count]; for (var i = 0; i < count; i++) arr[i] = cr.Double; return arr; } }

            public static implicit operator int[](RepeatReader rr) => rr.Int;
            public static implicit operator long[](RepeatReader rr) => rr.Long;
            public static implicit operator double[](RepeatReader rr) => rr.Double;
            public static implicit operator string[](RepeatReader rr) => rr.Ascii;
        }
        public RepeatReader Repeat(int count) => new RepeatReader(this, count);

        [DebuggerStepThrough]
        public struct SplitReader
        {
            ConsoleReader cr;
            public SplitReader(ConsoleReader cr) { this.cr = cr; }
            public string[] String { get { while (cr.buffer[cr.pos] <= 32) cr.MoveNext(); var list = new List<string>(); do { if (cr.buffer[cr.pos] < 32) cr.MoveNext(); else list.Add(cr.String); } while (cr.buffer[cr.pos] != 10 && cr.buffer[cr.pos] != 13); return list.ToArray(); } }
            public string[] Ascii { get { while (cr.buffer[cr.pos] <= 32) cr.MoveNext(); var list = new List<string>(); do { if (cr.buffer[cr.pos] < 32) cr.MoveNext(); else list.Add(cr.Ascii); } while (cr.buffer[cr.pos] != 10 && cr.buffer[cr.pos] != 13); return list.ToArray(); } }
            public int[] Int { get { while (cr.buffer[cr.pos] <= 32) cr.MoveNext(); var list = new List<int>(); do { if (cr.buffer[cr.pos] < 32) cr.MoveNext(); else list.Add(cr.Int); } while (cr.buffer[cr.pos] != 10 && cr.buffer[cr.pos] != 13); return list.ToArray(); } }
            public int[] Int0 { get { while (cr.buffer[cr.pos] <= 32) cr.MoveNext(); var list = new List<int>(); do { if (cr.buffer[cr.pos] < 32) cr.MoveNext(); else list.Add(cr.Int0); } while (cr.buffer[cr.pos] != 10 && cr.buffer[cr.pos] != 13); return list.ToArray(); } }
            public long[] Long { get { while (cr.buffer[cr.pos] <= 32) cr.MoveNext(); var list = new List<long>(); do { if (cr.buffer[cr.pos] < 32) cr.MoveNext(); else list.Add(cr.Long); } while (cr.buffer[cr.pos] != 10 && cr.buffer[cr.pos] != 13); return list.ToArray(); } }
            public long[] Long0 { get { while (cr.buffer[cr.pos] <= 32) cr.MoveNext(); var list = new List<long>(); do { if (cr.buffer[cr.pos] < 32) cr.MoveNext(); else list.Add(cr.Long0); } while (cr.buffer[cr.pos] != 10 && cr.buffer[cr.pos] != 13); return list.ToArray(); } }
            public double[] Double { get { while (cr.buffer[cr.pos] <= 32) cr.MoveNext(); var list = new List<double>(); do { if (cr.buffer[cr.pos] < 32) cr.MoveNext(); else list.Add(cr.Double); } while (cr.buffer[cr.pos] != 10 && cr.buffer[cr.pos] != 13); return list.ToArray(); } }

            public static implicit operator int[](SplitReader sr) => sr.Int;
            public static implicit operator long[](SplitReader sr) => sr.Long;
            public static implicit operator double[](SplitReader sr) => sr.Double;
            public static implicit operator string[](SplitReader sr) => sr.Ascii;
        }
        public SplitReader Split => new SplitReader(this);

        public static implicit operator int(ConsoleReader cr) => cr.Int;
        public static implicit operator long(ConsoleReader cr) => cr.Long;
        public static implicit operator double(ConsoleReader cr) => cr.Double;
        public static implicit operator string(ConsoleReader cr) => cr.Ascii;
    }
}
public class Program
{
    [System.Diagnostics.DebuggerBrowsable(System.Diagnostics.DebuggerBrowsableState.Never)] private ConsoleReader cr;

    public Program(ConsoleReader consoleReader) { this.cr = consoleReader; }
    static void Main() => Console.WriteLine(new Program(new ConsoleReader(Console.OpenStandardInput())).Result());
    #endregion
    public string Result() { var obj = Calc(); if (obj is bool) return (bool)obj ? "Yes" : "No"; if (obj is double) return ((double)obj).ToString("0.####################"); return obj.ToString(); }
    private object Calc()
    {

        long res = 0;
        N = cr;
        M = cr;

        var tate = cr.Repeat(N).Select<(int A, int B, int C)>(cr => (cr, cr, cr));
        var yoko = cr.Repeat(M).Select<(int D, int E, int F)>(cr => (cr, cr, cr));

        var xdic = Compress(tate.SelectMany(t => new[] { t.A, t.B }).Concat(yoko.Select(t => t.D)));
        var ydic = Compress(yoko.SelectMany(t => new[] { t.E, t.F }).Concat(tate.Select(t => t.C)));
        var xb = new int[xdic.Count];
        var yb = new int[ydic.Count];
        foreach (var (v, i) in xdic) xb[i] = v;
        foreach (var (v, i) in ydic) yb[i] = v;


        var yi = yb.UpperBound(0) - 1;
        var xi = xb.UpperBound(0) - 1;

        var r = ToInt(xi, yi);

        if (xi < 0 || yi < 0 || xb[xi] > 0 || yb[yi] > 0) return "INF";


        for (int x = -1; x <= xb.Length; x++)
        {
            uf.UnionSet(ToInt(x, -1), 0);
            uf.UnionSet(ToInt(x, yb.Length), 0);
        }
        for (int y = -1; y <= yb.Length; y++)
        {
            uf.UnionSet(ToInt(-1, y), 0);
            uf.UnionSet(ToInt(xb.Length, y), 0);
        }


        var tateWalls = NewArray(xb.Length + 1, yb.Length + 1, 0);
        var yokoWalls = NewArray(xb.Length + 1, yb.Length + 1, 0);
        foreach (var (A, B, C) in tate)
        {
            tateWalls[xdic[A] + 1][ydic[C] + 1]++;
            tateWalls[xdic[B] + 1][ydic[C] + 1]--;
        }
        foreach (var (D, E, F) in yoko)
        {
            yokoWalls[xdic[D] + 1][ydic[E] + 1]++;
            yokoWalls[xdic[D] + 1][ydic[F] + 1]--;
        }

        var tateSums = new Sums2D(tateWalls);
        var yokoSums = new Sums2D(yokoWalls);

        for (int x = 0; x < xb.Length; x++)
            for (int y = 0; y < yb.Length; y++)
            {
                if (tateSums[0, (x + 2), 0, (y + 2)] == tateSums[0, (x + 2), 0, (y + 1)])
                    uf.UnionSet(ToInt(x, y), ToInt(x, y - 1));
                if (yokoSums[0, (x + 2), 0, (y + 2)] == yokoSums[0, (x + 1), 0, (y + 2)])
                    uf.UnionSet(ToInt(x, y), ToInt(x - 1, y));
            }
        if (uf.IsSameSet(r, 0))
            return "INF";
        for (int x = 0; x < xb.Length - 1; x++)
            for (int y = 0; y < yb.Length - 1; y++)
                if (uf.IsSameSet(r, ToInt(x, y)))
                {
                    res += (long)(yb[y + 1] - yb[y]) * (xb[x + 1] - xb[x]);
                }
        return res;
    }
    int TupComp((int A, int B) t1, (int A, int B) t2) => t1.A.CompareTo(t2.A);
    int ToInt(int x, int y) => (x + 1) * gridLength + y + 1;
    int N;
    int M;
    const int gridLength = 3010;
    const int gridSize = gridLength * gridLength;
    UnionFind uf = new UnionFind(gridSize + 1);

    static Dictionary<T, int> Compress<T>(IEnumerable<T> orig) { var ox = new HashSet<T>(orig).ToArray(); if (typeof(IComparable<T>).IsAssignableFrom(typeof(T))) ox.Sort(); var zip = new Dictionary<T, int>(); for (int i = 0; i < ox.Length; i++) zip[ox[i]] = i; return zip; }
    static int[] Compressed<T>(T[] orig) => Compressed(orig, Compress(orig)); static int[] Compressed<T>(T[] orig, Dictionary<T, int> zip) { var res = new int[orig.Length]; for (int i = 0; i < res.Length; i++) res[i] = zip[orig[i]]; return res; }

}

static class 二分探索
{
    public static int BinarySearch(int ok, int ng, Predicate<int> isOK)
    {
        while (Math.Abs(ok - ng) > 1)
        {
            var m = (ok + ng) / 2;
            if (isOK(m)) ok = m;
            else ng = m;
        }
        return ok;
    }



    /* https://bitbucket.org/camypaper/complib/src/master/lib/Algorithms/BinarySearch.cs */
    /**
     * <summary>
     * 与えられた比較関数に従って，<paramref name="a"/> の要素のうち，<paramref name="v"/> 以上の要素であるような最小のインデックスを取得します．
     * </summary>
     * <typeparam name="T"><see cref="IList{T}"/> の要素の型を指定します．</typeparam>
     * <param name="a">対象となるコレクション</param>
     * <param name="v">対象となる要素</param>
     * <param name="f"></param>
     * <returns><paramref name="v"/> 以上の要素であるような最小の o-indexed でのインデックス．</returns>
     * <remarks> <paramref name="a"/> は比較関数に対して昇順であることを仮定しています．この関数は O(log N) で実行されます．</remarks>
    */
    public static int LowerBound<T>(this IList<T> a, T v, IComparer<T> cmp) => BinarySearch(a, v, cmp, true);

    /**
     * <summary>
     *　デフォルトの比較関数に従って，<paramref name="a"/> の要素のうち，<paramref name="v"/> 以上の要素であるような最小のインデックスを取得します．
     * </summary>
     * <typeparam name="T"><see cref="IList{T}"/> の要素の型を指定します．</typeparam>
     * <param name="a">対象となるコレクション</param>
     * <param name="v">対象となる要素</param>
     * <param name="f"></param>
     * <returns><paramref name="v"/> 以上の要素であるような最小の o-indexed でのインデックス．</returns>
     * <remarks> <paramref name="a"/> は比較関数に対して昇順であることを仮定しています．この関数は O(log N) で実行されます．</remarks>
    */
    public static int LowerBound<T>(this IList<T> a, T v) => BinarySearch(a, v, Comparer<T>.Default, true);

    /**
     * <summary>
     * 与えられた比較関数に従って，<paramref name="a"/> の要素のうち，<paramref name="v"/> より真に大きい要素が現れる最小のインデックスを取得します．
     * </summary>
     * <typeparam name="T"><see cref="IList{T}"/> の要素の型を指定します．</typeparam>
     * <param name="a">対象となるコレクション</param>
     * <param name="v">対象となる要素</param>
     * <param name="f"></param>
     * <returns><paramref name="v"/> 以上の要素であるような最小の o-indexed でのインデックス．</returns>
     * <remarks> <paramref name="a"/> は比較関数に対して昇順であることを仮定しています．この関数は O(log N) で実行されます．</remarks>
    */
    public static int UpperBound<T>(this IList<T> a, T v, IComparer<T> cmp) => BinarySearch(a, v, cmp, false);

    /**
     * <summary>
     *　デフォルトの比較関数に従って，<paramref name="a"/> の要素のうち，<paramref name="v"/> より真に大きい要素が現れる最小のインデックスを取得します．
     * </summary>
     * <typeparam name="T"><see cref="IList{T}"/> の要素の型を指定します．</typeparam>
     * <param name="a">対象となるコレクション</param>
     * <param name="v">対象となる要素</param>
     * <param name="f"></param>
     * <returns><paramref name="v"/> 以上の要素であるような最小の o-indexed でのインデックス．</returns>
     * <remarks> <paramref name="a"/> は比較関数に対して昇順であることを仮定しています．この関数は O(log N) で実行されます．</remarks>
    */
    public static int UpperBound<T>(this IList<T> a, T v) => BinarySearch(a, v, Comparer<T>.Default, false);

    private static int BinarySearch<T>(this IList<T> a, T v, IComparer<T> cmp, bool isLowerBound)
    {
        int ok = a.Count;
        int ng = -1;
        while (ok - ng > 1)
        {
            var m = (ok + ng) / 2;
            var c = cmp.Compare(a[m], v);
            if (c > 0 || (c == 0 && isLowerBound)) ok = m;
            else ng = m;
        }
        return ok;
    }
}

class UnionFind { int[] data; public UnionFind(int size) { this.data = NewArray(size, -1); } public int Root(int x) { if (data[x] < 0) return x; return data[x] = Root(data[x]); } public int Count(int x) => -data[Root(x)]; public void UnionSet(int x, int y) => TryUnionSet(x, y); public bool TryUnionSet(int x, int y) { var xRoot = Root(x); var yRoot = Root(y); if (xRoot == yRoot) return false; else if (data[yRoot] < data[xRoot])/*y側の方が多い場合は逆にする*/ (xRoot, yRoot) = (yRoot, xRoot); data[xRoot] += data[yRoot]; data[yRoot] = xRoot; return true; } public bool IsSameSet(int x, int y) => Root(x) == Root(y); }


class Sums2D
{
    private long[][] impl;
    public int Length1 { get; }
    public int Length2 { get; }
    public Sums2D(int[][] arr)
    {
        this.Length1 = arr.Length;
        this.Length2 = arr[0].Length;
        impl = NewArray(Length1 + 1, Length2 + 1, 0L);
        for (var i = 0; i < Length1; i++)
            for (var j = 0; j < Length2; j++)
                impl[i + 1][j + 1] = impl[i + 1][j] + impl[i][j + 1] - impl[i][j] + arr[i][j];
    }
    public long this[int left, int rightExclusive, int top, int bottomExclusive]
    {
        get
        {
            return impl[rightExclusive][bottomExclusive]
              - impl[left][bottomExclusive]
              - impl[rightExclusive][top]
              + impl[left][top];
        }
    }
}
static class DicExt
{
    public static void Deconstruct<TKey, TValue>(this KeyValuePair<TKey, TValue> pair, out TKey key, out TValue val)
    {
        key = pair.Key;
        val = pair.Value;
    }
}
