#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 Unsafe = System.Runtime.CompilerServices.Unsafe;
using BigInteger = System.Numerics.BigInteger;
using StringBuilder = System.Text.StringBuilder;
using static AtCoderProject.Global;
using static AtCoderProject.NumGlobal;
using System.Runtime.InteropServices;

namespace AtCoderProject { public static class Global { 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 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(ReadOnlySpan<char> s) { /* 自前実装の方が速い */ BigInteger res; if (s.Length % 9 == 0) res = 0; else { res = new BigInteger(int.Parse(s.Slice(0, s.Length % 9))); s = s.Slice(s.Length % 9); } while (s.Length > 0) { var sp = s.Slice(0, 9); res *= 1000_000_000; res += int.Parse(sp); s = s.Slice(9); } 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 bool UpdateMax(this ref int r, int val) { if (r < val) { r = val; return true; } return false; } public static bool UpdateMax(this ref long r, long val) { if (r < val) { r = val; return true; } return false; } public static bool UpdateMin(this ref int r, int val) { if (r > val) { r = val; return true; } return false; } public static bool UpdateMin(this ref long r, long val) { if (r > val) { r = val; return true; } return false; } public static long ToLong(this int i) => i; public static T[] Fill<T>(this T[] arr, T value) { Array.Fill(arr, 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 (int index, T max) 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 (maxIndex, max); } public static (TSource item, TMax max) 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 (maxByItem, max); } public static (int index, T min) 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 (minIndex, min); } public static (TSource item, TMin min) 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 (minByItem, min); } 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) { dic.TryGetValue(key, out var v); return v; } public static TValue GetOrInit<TKey, TValue>(this Dictionary<TKey, TValue> dic, TKey key, TValue value) { if (dic.TryGetValue(key, out var 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) { this.collection = collection ?? throw new ArgumentNullException(nameof(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 void Deconstruct(out ConsoleReader o1, out ConsoleReader o2) => (o1, o2) = (this, this); public void Deconstruct(out ConsoleReader o1, out ConsoleReader o2, out ConsoleReader o3) => (o1, o2, o3) = (this, this, this); public void Deconstruct(out ConsoleReader o1, out ConsoleReader o2, out ConsoleReader o3, out ConsoleReader o4) => (o1, o2, o3, o4) = (this, this, this, this); public void Deconstruct(out ConsoleReader o1, out ConsoleReader o2, out ConsoleReader o3, out ConsoleReader o4, out ConsoleReader o5) => (o1, o2, o3, o4, o5) = (this, this, this, this, this); public void Deconstruct(out ConsoleReader o1, out ConsoleReader o2, out ConsoleReader o3, out ConsoleReader o4, out ConsoleReader o5, out ConsoleReader o6) => (o1, o2, o3, o4, o5, o6) = (this, this, this, this, this, this); public void Deconstruct(out ConsoleReader o1, out ConsoleReader o2, out ConsoleReader o3, out ConsoleReader o4, out ConsoleReader o5, out ConsoleReader o6, out ConsoleReader o7) => (o1, o2, o3, o4, o5, o6, o7) = (this, this, this, this, this, this, this); public void Deconstruct(out ConsoleReader o1, out ConsoleReader o2, out ConsoleReader o3, out ConsoleReader o4, out ConsoleReader o5, out ConsoleReader o6, out ConsoleReader o7, out ConsoleReader o8) => (o1, o2, o3, o4, o5, o6, o7, o8) = (this, this, this, this, this, this, this, this); } }
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() => Calc() switch { bool b => b ? "Yes" : "No", double d => d.ToString("0.####################"), object o => o.ToString(), };
    public object Calc()
    {
        N = cr;
        M = cr;
        {
            var tateList = cr.Repeat(N).Select<(int A, int B, int C)>(cr => (cr, cr, cr)).ToList();
            var yokoList = cr.Repeat(M).Select<(int D, int E, int F)>(cr => (cr, cr, cr)).ToList();
            var yokoD = yokoList.Select(t => t.D).ToArray().Sort();

            for (int i = tateList.Count - 1; i >= 0; i--)
            {
                var ai = yokoD.LowerBound(tateList[i].A);
                if (ai >= yokoD.Length)
                {
                    tateList.RemoveAt(i);
                    continue;
                }

                var bi = yokoD.UpperBound(tateList[i].B) - 1;
                if (bi < 0)
                {
                    tateList.RemoveAt(i);
                    continue;
                }

                tateList[i] = (yokoD[ai], yokoD[bi], tateList[i].C);
            }

            var tateC = tateList.Select(t => t.C).ToArray().Sort();
            for (int i = yokoList.Count - 1; i >= 0; i--)
            {
                var ai = tateC.LowerBound(yokoList[i].E);
                if (ai >= tateC.Length)
                {
                    yokoList.RemoveAt(i);
                    continue;
                }
                var bi = tateC.UpperBound(yokoList[i].F) - 1;
                if (bi < 0)
                {
                    yokoList.RemoveAt(i);
                    continue;
                }
                yokoList[i] = (yokoList[i].D, tateC[ai], tateC[bi]);
            }

            //var tate = tateList.ToArray().Sort(t => t.C);
            //var yoko = yokoList.ToArray().Sort(t => t.D);
            cc = Compress(tateList.Select(t => t.C));
            dc = Compress(yokoList.Select(t => t.D));
            bc = new int[cc.Count];
            bd = new int[dc.Count];
            foreach (var (v, i) in cc) bc[i] = v;
            foreach (var (v, i) in dc) bd[i] = v;

            tate = NewArray(bc.Length, () => new List<ValueTuple<int, int>>());
            yoko = NewArray(bd.Length, () => new List<ValueTuple<int, int>>());
            foreach (var (A, B, C) in tateList)
                tate[cc[C]].Add((A, B));
            foreach (var (D, E, F) in yokoList)
                yoko[dc[D]].Add((E, F));
        }
        foreach (var l in tate) l.Sort(TupComp);
        foreach (var l in yoko) l.Sort(TupComp);

        if (bc[0] >= 0 || bc[^1] <= 0 || bd[0] >= 0 || bd[^1] <= 0) return "INF";

        var gridSize = (tate.Length - 1) * (yoko.Length - 1);
        uf = new UnionFind(gridSize + 1);
        {
            int cur;
            cur = 0;
            for (int x = 0; x < yoko.Length - 1; x++)
            {
                while (cur < tate[0].Count && bd[x] >= tate[0][cur].B)
                    cur++;
                if (cur >= tate[0].Count || (bd[x] < tate[0][cur].A || tate[0][cur].B <= bd[x]))
                    uf.UnionSet(ToInt(x, 0), gridSize);
            }
            cur = 0;
            for (int x = 0; x < yoko.Length - 1; x++)
            {
                while (cur < tate[^1].Count && bd[x] >= tate[^1][cur].B)
                    cur++;
                if (cur >= tate[^1].Count || (bd[x] < tate[^1][cur].A || tate[^1][cur].B <= bd[x]))
                    uf.UnionSet(ToInt(x, tate.Length - 2), gridSize);
            }

            cur = 0;
            for (int y = 0; y < tate.Length - 1; y++)
            {
                while (cur < yoko[0].Count && bc[y] >= yoko[0][cur].F)
                    cur++;
                if (cur >= yoko[0].Count || (bc[y] < yoko[0][cur].E || yoko[0][cur].F <= bc[y]))
                    uf.UnionSet(ToInt(0, y), gridSize);
            }
            cur = 0;
            for (int y = 0; y < tate.Length - 1; y++)
            {
                while (cur < yoko[^1].Count && bc[y] >= yoko[^1][cur].F)
                    cur++;
                if (cur >= yoko[^1].Count || (bc[y] < yoko[^1][cur].E || yoko[^1][cur].F <= bc[y]))
                    uf.UnionSet(ToInt(yoko.Length - 2, y), gridSize);
            }
        }
        {
            int cur;

            // 左
            for (int y = 1; y < tate.Length - 1; y++)
            {
                cur = 0;
                for (int x = 0; x < yoko.Length - 1; x++)
                {
                    while (cur < tate[y].Count && bd[x] >= tate[y][cur].B)
                        cur++;
                    if (cur >= tate[y].Count || (bd[x] < tate[y][cur].A || tate[y][cur].B <= bd[x]))
                        uf.UnionSet(ToInt(x, y), ToInt(x, y - 1));
                }
            }

            // 上
            for (int x = 1; x < yoko.Length - 1; x++)
            {
                cur = 0;
                for (int y = 0; y < tate.Length - 1; y++)
                {
                    while (cur < yoko[x].Count && bc[y] >= yoko[x][cur].F)
                        cur++;
                    if (cur >= yoko[x].Count || (bc[y] < yoko[x][cur].E || yoko[x][cur].F <= bc[y]))
                        uf.UnionSet(ToInt(x, y), ToInt(x - 1, y));
                }
            }
        }
        var yi = bc.UpperBound(0) - 1;
        var xi = bd.UpperBound(0) - 1;

        var r = ToInt(xi, yi);
        long res = 0;
        for (int x = 0; x < yoko.Length - 1; x++)
            for (int y = 0; y < tate.Length - 1; y++)
                if (uf.IsSameSet(r, ToInt(x, y)))
                {
                    res += (long)(bc[y + 1] - bc[y]) * (bd[x + 1] - bd[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 * (tate.Length - 1) + y;
    List<(int A, int B)>[] tate;
    List<(int E, int F)>[] yoko;
    Dictionary<int, int> cc;
    Dictionary<int, int> dc;
    int[] bc;
    int[] bd;
    int N;
    int M;
    UnionFind uf;

    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); }
