using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Text.RegularExpressions;
using System.IO;






class readint
{



    public readint(out int i)
    {
        i = int.Parse(Console.ReadLine());

    }
    public readint(out int a, out int b)
    {
        int[] sp = Console.ReadLine().Split().Select(int.Parse).ToArray();
        a = sp[0];
        b = sp[1];

    }
    public readint(out int a, out int b, out int c)
    {
        int[] sp = Console.ReadLine().Split().Select(int.Parse).ToArray();
        a = sp[0];
        b = sp[1];
        c = sp[2];
    }
    public readint(out int a, out int b, out int c, out int d)
    {
        int[] sp = Console.ReadLine().Split().Select(int.Parse).ToArray();
        a = sp[0];
        b = sp[1];
        c = sp[2];
        d = sp[3];

    }

}

class readlong
{


    public readlong(out long i)
    {
        i = long.Parse(Console.ReadLine());

    }
    public readlong(out long a, out long b)
    {
        long[] sp = Console.ReadLine().Split().Select(long.Parse).ToArray();
        a = sp[0];
        b = sp[1];

    }
    public readlong(out long a, out long b, out long c)
    {
        long[] sp = Console.ReadLine().Split().Select(long.Parse).ToArray();
        a = sp[0];
        b = sp[1];
        c = sp[2];
    }
    public readlong(out long a, out long b, out long c, out long d)
    {
        long[] sp = Console.ReadLine().Split().Select(long.Parse).ToArray();
        a = sp[0];
        b = sp[1];
        c = sp[2];
        d = sp[3];

    }

}

class modMWorld
{
    public static long M = (int)Math.Pow(10, 9) + 7;

    //必要な演算は、加減乗除、nCk,n!,a^n
    public static long add(long a, long b)
    {
        long sum = a + b;
        sum += M;
        return sum % M;

    }
    public static long sub(long a, long b)
    {
        long dif = a - b;
        dif += M * 2;
        return dif % M;

    }

    public static long mul(long a, long b)
    {
        long product = a;
        product *= b;
        return product % M;

    }

    public static long div(long a, long b)
    {
        return mul(a, Pow(b, M - 2));

    }

    public static long modify(long a)
    {

        return (a % M + M) % M;
    }
    /// <summary>
    /// a^m modMを求める
    /// </summary>
    /// <param name="a"></param>
    /// <param name="m"></param>
    /// <returns></returns>
    public static long Pow(long a, long m)
    {
        switch (m)
        {
            case 0:
                return 1;
            case 1:
                return a;
            default:
                long p1 = Pow(a, m / 2);
                long p2 = mul(p1, p1);
                return ((m % 2) == 0) ? p2 : mul(p2, a);
        }
    }


    public static long kaijou(long n)
    {
        //!
        long output = 1;
        for (int i = 0; i < n; i++)
        {
            output = mul(output, n - i);
        }
        return output;

    }

    public static long nCk(long n, long k)
    {
        long output = 1;
        for (int i = 1; i <= k; i++)
        {
            output = mul(output, n - (i - 1));
            output = div(output, i);

        }
        return output;
    }

}




class Util
{

    public static string convertToBinary(int N, int length)
    {
        string binary = Convert.ToString(N, 2);
        while (length > binary.Length)
        {
            binary = "0" + binary;
        }
        return binary;
    }


    public static int[] readintarr()
    {
        return Console.ReadLine().Split().Select(int.Parse).ToArray();
    }

    public static long[] readlongarr()
    {
        return Console.ReadLine().Split().Select(long.Parse).ToArray();
    }

    /// <summary>
    /// nの約数を小さい順のリストで返します。
    /// </summary>
    /// <param name="n"></param>
    /// <returns></returns>
    public static List<int> make_divisor(int n)
    {
        List<int> output = new List<int>();
        for (int i = 1; i <= Math.Sqrt(n) + 1; i++)
        {
            if (n % i == 0)
            {
                output.Add(i);
                if (i * i != n)
                {
                    output.Add(n / i);
                }
            }

        }
        output.Sort();
        return output;

    }

    //iの素因数分解をします
    public static List<int> soinsuuBunkai(int n)
    {
        //素因数分解をします
        List<int> output = new List<int>();
        int target = n;
        for (int i = 2; i <= 1 + Math.Sqrt(target); i += 2)
        {
            while (target % i == 0)
            {
                target /= i;
                output.Add(i);

            }
            if (i == 2) i--;

        }
        if (target > 1)
        {
            output.Add(target);
        }
        return output;

    }

    public static List<long> soinsuuBunkai(long n)
    {
        List<long> output = new List<long>();
        long target = n;
        for (int i = 2; i <= 1 + Math.Sqrt(target); i += 2)
        {
            while (target % i == 0)
            {
                target /= i;
                output.Add(i);

            }
            if (i == 2) i--;

        }
        if (target > 1)
        {
            output.Add(target);
        }
        return output;


    }


    /// <summary>
    /// 2引数の最大公約数を返します。longです。
    /// </summary>
    /// <param name="a">long 引数1</param>
    /// <param name="b">long 引数2</param>
    /// <returns></returns>
    public static long GCD(long a, long b)
    {
        if (a < b)
            swap(ref a, ref b);
        if (a % b == 0) return b;
        return GCD(b, a % b);

    }
    /// <summary>
    /// 2引数の最大公約数を返します。intです。
    /// </summary>
    /// <param name="a">int 引数1</param>
    /// <param name="b">int 引数2</param>
    /// <returns></returns>
    public static int GCD(int a, int b)
    {
        //if (a < b)
        //swap(ref a, ref b);
        if (a % b == 0) return b;
        return GCD(b, a % b);
    }

    /// <summary>
    /// 2つの変数の中身を交換する。型はなんでもいい
    /// </summary>
    /// <typeparam name="T"></typeparam>
    /// <param name="a"></param>
    /// <param name="b"></param>
    public static void swap<T>(ref T a, ref T b)
    {
        T temp = b;
        b = a;
        a = temp;

    }


    /// <summary>
    /// 2引数の最大公約数を返します。
    /// </summary>
    /// <param name="a"></param>
    /// <param name="b"></param>
    /// <returns></returns>
    public static long LCM(long a, long b)
    {
        return a * b / GCD(a, b);
    }
    /// <summary>
    /// 2引数の最大公約数を返します。
    /// </summary>
    /// <param name="a"></param>
    /// <param name="b"></param>
    /// <returns></returns>
    public static long LCM(int a, int b)
    {
        return Math.BigMul(a, b) / GCD(a, b);
    }


    public static int M = (int)998244353;//(Math.Pow(10, 9)) + 7;
    private static int[] factorial_modM;

    public static long nCr(long n, long r)
    {
        long output = 1;
        for (int i = 1; i <= r; i++)
        {
            output *= (n + 1 - i);
            output /= (i);

        }
        return output;
    }


    /// <summary>
    /// 2引数の積 mod Mを求める。Mは10億7。
    /// 変えられるよ。
    /// </summary>
    /// <param name="a"></param>
    /// <param name="b"></param>
    /// <returns></returns>
    public static int Multiple_modM(int a, int b)
    {
        return (int)(Math.BigMul(a, b) % M);
    }
    /// <summary>
    /// n! modMまたはnCmを求めるための準備を行う。引数は最大値。
    /// </summary>
    /// <param name="n"></param>
    public static void factorial_modM_Prepare(int n)
    {
        factorial_modM = new int[n + 1];
        factorial_modM[0] = 1;
        for (int i = 1; i <= n; ++i)
        {
            factorial_modM[i] = Multiple_modM(factorial_modM[i - 1], i);
        }
    }

    /// <summary>
    /// n! mod M を返す。やる前にfactorial_modM_Prepare(n)を実行しといてね。
    /// </summary>
    /// <param name="n"></param>
    /// <returns></returns>
    public static int Factorial(int n)
    {
        return factorial_modM[n];
    }

    /// <summary>
    /// a^m modMを求める
    /// </summary>
    /// <param name="a"></param>
    /// <param name="m"></param>
    /// <returns></returns>
    public static int Pow(int a, int m)
    {
        switch (m)
        {
            case 0:
                return 1;
            case 1:
                return a;
            default:
                int p1 = Pow(a, m / 2);
                int p2 = Multiple_modM(p1, p1);
                return ((m % 2) == 0) ? p2 : Multiple_modM(p2, a);
        }
    }
    /// <summary>
    /// a / m Mod M を求める。
    /// </summary>
    /// <param name="a"></param>
    /// <param name="b"></param>
    /// <returns></returns>
    public static int Div(int a, int b)
    {
        return Multiple_modM(a, Pow(b, M - 2));
    }
    /// <summary>
    /// nCr mod M を求める。やる前にfactorial_modM_Prepare(n)を実行しといてね。
    /// </summary>
    /// <param name="n"></param>
    /// <param name="r"></param>
    /// <returns></returns>
    public static int nCr_modM(int n, int r)
    {
        if (r < 0) return 0;

        if (n < r) { return 0; }
        if (n == r) { return 1; }
        int res = Factorial(n);
        res = Div(res, Factorial(r));
        res = Div(res, Factorial(n - r));
        return res;
    }

}
/// <summary>
/// Union-Find木を定義する。コンストラクタの指定は、頂点の番号。
/// おすすめとしては、UnionFind<T>[] で宣言してしまう。
/// 配列で宣言したあと、コンストラクタ使ってnewするのを忘れないでね。
/// コンストラクタのitemは、そのノード固有のIDになるので、絶対必要です
/// </summary>
/// <typeparam name="T">int固定でいいよね。</typeparam>
class UnionFind<T>
{
    public int tree_height;
    public UnionFind<T> parent;
    public T item
    {
        get;
        private set;
    }

    public UnionFind(T item)
    {
        tree_height = 0;
        parent = this;
        this.item = item;
    }

    /// <summary>
    /// 一番上の親を探す。
    /// 探しながら繋がり方を最適化している。
    /// UnionFindの頂点そのものを返すので、==での比較が可能。
    /// </summary>
    /// <returns></returns>
    public UnionFind<T> FindAdam()
    {
        if (parent == this) return this;
        else
        {
            UnionFind<T> ParentOfParent = parent.FindAdam();
            parent = ParentOfParent;//縦長な構成をつなぎ直している
            return ParentOfParent;
        }
    }
    /// <summary>
    /// unionfind2つを一つにつなぐ。
    /// </summary>
    /// <param name="a"></param>
    /// <param name="b"></param>
    public static void Unite(UnionFind<T> a, UnionFind<T> b)
    {
        UnionFind<T> ParentOfA = a.FindAdam();
        UnionFind<T> ParentOfB = b.FindAdam();
        if (ParentOfA.tree_height < ParentOfB.tree_height)
        {
            ParentOfA.parent = ParentOfB;
            ParentOfB.tree_height = Math.Max(ParentOfA.tree_height + 1, ParentOfB.tree_height);
        }
        else
        {
            ParentOfB.parent = ParentOfA;
            ParentOfA.tree_height = Math.Max(ParentOfB.tree_height + 1, ParentOfA.tree_height);
        }

    }



}

//Treap 平衡二分木
class Treap<T> where T : IComparable
{
    private class Node
    {
        private static Random g_rand = new Random();
        private readonly int m_rank = g_rand.Next();
        private readonly T m_value;
        private Node m_lch;
        private Node m_rch;
        private int m_count;

        public Node(T value)
        {
            m_value = value;
            m_count = 1;
        }

        private static int Count(Node node)
        {
            return (node != null) ? node.m_count : 0;
        }

        private Node Update()
        {
            m_count = Count(m_lch) + Count(m_rch) + 1;
            return this;
        }

        public static Node Merge(Node a, Node b)
        {
            if (a == null) { return b; }
            if (b == null) { return a; }

            if (a.m_rank < b.m_rank)
            {
                a.m_rch = Merge(a.m_rch, b);
                return a.Update();
            }
            else
            {
                b.m_lch = Merge(a, b.m_lch);
                return b.Update();
            }
        }

        public static Tuple<Node, Node> Split(Node t, int k)
        {
            if (t == null) { return new Tuple<Node, Node>(null, null); }

            if (k <= Count(t.m_lch))
            {
                var pair = Split(t.m_lch, k);
                t.m_lch = pair.Item2;
                return new Tuple<Node, Node>(pair.Item1, t.Update());
            }
            else
            {
                var pair = Split(t.m_rch, k - Count(t.m_lch) - 1);
                t.m_rch = pair.Item1;
                return new Tuple<Node, Node>(t.Update(), pair.Item2);
            }
        }

        public int FindIndex(T value)
        {
            int L = Count(m_lch);
            if (value.CompareTo(m_value) < 0)
            {
                return (m_lch != null) ? m_lch.FindIndex(value) : 0;
            }
            else if (value.CompareTo(m_value) > 0)
            {
                return (m_rch != null) ? m_rch.FindIndex(value) + L + 1 : L + 1;
            }
            else
            {
                return L;
            }
        }

        public T this[int i]
        {
            get
            {
                int L = Count(m_lch);
                if (i < L)
                {
                    return m_lch[i];
                }
                else if (i > L)
                {
                    return m_rch[i - L - 1];
                }
                else
                {
                    return m_value;
                }
            }
        }
    }

    private Node node;

    public void Insert(T value)
    {
        if (node != null)
        {
            int k = node.FindIndex(value);
            var pair = Node.Split(node, k);
            node = Node.Merge(Node.Merge(pair.Item1, new Node(value)), pair.Item2);
        }
        else
        {
            node = new Node(value);
        }
    }

    public int FindIndex(T value)
    {
        return node.FindIndex(value);
    }

    public T this[int i]
    {
        get
        {
            return node[i];
        }
    }
}


/// <summary>
/// 使い方:Permutation.next(配列)　で次の配列を返す
/// 配列を受け取って、その配列の要素を全部使った組み合わせのうち、辞書順で次のものを返します。
/// もし、次のがない場合、空の配列を返します。
/// 
/// </summary>
/// <typeparam name="T"></typeparam>
class Permutation<T> where T : IComparable
{


    public static T[] next(T[] letters)
    {
        int pivot = -1;
        for (int i = letters.Length - 2; i >= 0; i--)
        {
            if (letters[i].CompareTo(letters[i + 1]) < 0)
            {
                pivot = i;
                break;
            }

        }
        if (pivot == -1)
        {
            return new T[0];
        }

        int big_min = letters.Length - 1;
        T big_min_T = letters[letters.Length - 1];
        for (int i = letters.Length - 1; i > pivot; i--)
        {//big_min_Tより小さいかつ、pivotのより大きい
            if (letters[pivot].CompareTo(letters[i]) > 0 && letters[pivot].CompareTo(big_min_T) < 0)
            {
                big_min_T = letters[i];
                big_min = i;

            }

        }

        T temp = letters[pivot];
        letters[pivot] = letters[big_min];
        letters[big_min] = temp;

        Array.Sort(letters, pivot + 1, letters.Length - pivot - 1);


        return letters;
    }

}

/// <summary>
/// 使い方 : Combination .AllCombination(使える文字を、小さい順から配列にしたもの,ほしい文字数)
/// 使える文字を、小さい順から配列にしたものを重複ありで組み合わせて、stringのlistで出力する
///
/// </summary>
/// <typeparam name="T"></typeparam>
class Combination<T> where T : IComparable
{
    private static bool stop = false;
    public static List<string> AllCombination(T[] letters, int n)
    {
        //n桁ですよね。
        List<string> outlist = new List<string>();
        T[] state = new T[n];
        for (int i = 0; i < n; i++)
        {
            state[i] = letters[0];
        }
        outlist.Add(String.Join(" ", state));

        while (true)
        {
            next_keta(ref state, state.Length - 1, letters);
            if (stop) break;
            outlist.Add(string.Join(" ", state));


        }

        return outlist;

    }

    public static T[] next_keta(ref T[] state, int keta, T[] letters)
    {
        if (keta == -1)
        {
            stop = true;
            return new T[0];
        }
        if (state[keta].CompareTo(letters[letters.Length - 1]) == 0)
        {

            //見た桁を最初の要素にする処理を
            state[keta] = letters[0];
            return next_keta(ref state, keta - 1, letters);
        }
        else
        {
            int ketaindex = 0;
            for (int i = 0; i < letters.Length; i++)
            {
                if (state[keta].CompareTo(letters[i]) == 0)
                {
                    ketaindex = i;
                    break;

                }
            }
            state[keta] = letters[ketaindex + 1];
            return state;
        }
    }

}


/// <summary>
/// long
/// </summary>
class BinaryDictionary
{
    public Dictionary<long, long> dict = new Dictionary<long, long>();
    public phantaSortedList<long> keys = new phantaSortedList<long>();


    public bool ContainsKey(int x)
    {
        return (keys.indexSearch((long)x) != -1);

    }
    public bool ContainsKey(long x)
    {
        return (keys.indexSearch((long)x) != -1);
    }

    public void Add(int x)
    {
        this.Add((long)x);
    }
    public void Add(long x)
    {
        if (ContainsKey(x))
        {
            dict[x] += 1;
        }
        else
        {
            dict[x] = 1;
            keys.Add(x);
        }
    }

    public long Value(int key)
    {
        return dict[key];
    }
    public long Value(long key)
    {
        return dict[key];
    }

}

/// <summary>
/// 常に昇順に並んでいるすごいやつだよ
/// 
/// </summary>
/// <typeparam name="T"></typeparam>
class phantaSortedList<T>
{
    public List<T> list;
    readonly Comparison<T> cmp = Comparer<T>.Default.Compare;
    public phantaSortedList()
    {
        list = new List<T>();



    }

    public void Add(T x)
    {
        if (this.list.Count == 0)
        {
            list.Add(x);
            return;
        }

        int left = -1;
        int right = this.list.Count;
        while (right - left > 1)
        {
            int target = (right + left) / 2;
            if (cmp(list[target], x) >= 0)
            {
                right = target;

            }
            else
            {
                left = target;
            }

        }
        //同じものを指しているか、１違うものを指しているはず。

        if (left == -1)
        {
            if (cmp(list[0], x) >= 0)
            {
                list.Insert(0, x);
            }
            else
            {
                list.Insert(1, x);
            }
        }
        else if (right == this.list.Count)
        {
            if (cmp(list[this.list.Count - 1], x) >= 0)
            {
                list.Insert(this.list.Count - 2, x);
            }
            else
            {
                list.Add(x);
            }
        }
        else
        {
            list.Insert(right, x);
        }

    }

    /// <summary>
    /// xがあるならその最小indexを。ないなら-1を。
    /// </summary>
    /// <param name="x"></param>
    /// <returns></returns>
    public int indexSearch(T x)
    {
        if (list.Count == 0)
        {
            return -1;
        }
        int ok = list.Count;
        int ng = -1;
        while (ok - ng > 1)
        {
            int mid = (ok + ng) / 2;
            if (cmp(list[mid], x) >= 0)
            {
                ok = mid;
            }
            else
            {
                ng = mid;
            }

        }
        if (ok == list.Count)
        {

            //リストの中にあるすべてのものより大きいものを検索した場合
            return -1;
        }
        else if (cmp(list[ok], x) == 0)
        {
            return ok;
        }
        else
        {
            return -1;
        }

    }


    /// <summary>
    /// あるなら一つ削除。ないなら無視。
    /// </summary>
    /// <param name="x"></param>
    public void Remove(T x)
    {
        if (list.Count == 0)
        {
            return;
        }


        int left = -1;
        int right = this.list.Count;
        while (right - left > 1)
        {
            int target = (right + left) / 2;
            if (cmp(list[target], x) >= 0)
            {
                right = target;

            }
            else
            {
                left = target;
            }

        }
        //同じものを指しているか、１違うものを指しているはず。

        {
            if (left == -1)
            {
                if (cmp(list[0], x) == 0)
                {
                    list.RemoveAt(0);
                }
            }
            else if (right == this.list.Count)
            {
                if (cmp(list.Last(), x) == 0)
                {
                    list.RemoveAt(list.Count - 1);
                }

            }
            else
            {
                if (cmp(list[right], x) == 0)
                {
                    list.RemoveAt(right);
                }

            }
        }



    }
    /// <summary>
    /// 指定した値をlistから全滅させます。
    /// </summary>
    /// <param name="x"></param>
    public void allRemove(T x)
    {
        if (list.Count == 0)
        {
            return;
        }


        int left = -1;
        int right = this.list.Count;
        while (right - left > 1)
        {
            int target = (right + left) / 2;
            if (cmp(list[target], x) >= 0)
            {
                right = target;

            }
            else
            {
                left = target;
            }

        }
        //同じものを指しているか、１違うものを指しているはず。

        {
            if (left == -1)
            {
                while (cmp(list[0], x) == 0)
                {
                    list.RemoveAt(0);
                }
            }
            else if (right == this.list.Count)
            {
                while (cmp(list.Last(), x) == 0)
                {
                    list.RemoveAt(list.Count - 1);
                }

            }
            else
            {
                while (right < list.Count)
                {
                    if (cmp(list[right], x) == 0)
                    {
                        list.RemoveAt(right);
                    }
                    else
                    {
                        break;
                    }
                }
            }
        }



    }

    public T min()
    {
        if (list.Count == 0) return default(T);
        return list[0];
    }
    public T max()
    {

        if (list.Count == 0) return default(T);
        return list.Last();
    }


}


namespace CompLib.Collections
{
    #region PriorityQueue
    /// <summary>
    /// 指定した型のインスタンスを最も価値が低い順に取り出すことが可能な可変サイズのコレクションを表します．
    /// </summary>
    /// <typeparam name="T">優先度付きキュー内の要素の型を指定します．</typeparam>
    /// <remarks>内部的にはバイナリヒープによって実装されています．</remarks>
    public class PriorityQueue<T>
    {
        readonly List<T> heap = new List<T>();
        readonly Comparison<T> cmp;

        /// <summary>
        /// デフォルトの比較子を使用してインスタンスを初期化します．
        /// </summary>
        /// <remarks>この操作は O(1) で実行されます．</remarks>
        public PriorityQueue() { cmp = Comparer<T>.Default.Compare; }

        /// <summary>
        /// デリゲートで表されるような比較関数を使用してインスタンスを初期化します．
        /// </summary>
        /// <param name="comparison"></param>
        /// <remarks>この操作は O(1) で実行されます．</remarks>
        public PriorityQueue(Comparison<T> comparison) { cmp = comparison; }

        /// <summary>
        /// 指定された比較子を使用してインスタンスを初期化します．
        /// </summary>
        /// <param name="comparer"></param>
        /// <remarks>この操作は O(1) で実行されます．</remarks>
        public PriorityQueue(IComparer<T> comparer) { cmp = comparer.Compare; }

        /// <summary>
        /// 優先度付きキューに要素を追加します．
        /// </summary>
        /// <param name="item">優先度付きキューに追加される要素</param>
        /// <remarks>最悪計算量 O(log N) で実行されます．</remarks>
        public void Enqueue(T item)
        {
            var pos = heap.Count;
            heap.Add(item);
            while (pos > 0)
            {
                var par = (pos - 1) / 2;
                if (cmp(heap[par], item) <= 0)
                    break;
                heap[pos] = heap[par];
                pos = par;
            }
            heap[pos] = item;

        }

        /// <summary>
        /// 優先度付きキューから最も価値が低い要素を削除し，返します．
        /// </summary>
        /// <returns>優先度付きキューから削除された要素．</returns>
        /// <remarks>最悪計算量 O(log N) で実行されます．</remarks>
        public T Dequeue()
        {
            var ret = heap[0];
            var pos = 0;
            var x = heap[heap.Count - 1];

            while (pos * 2 + 1 < heap.Count - 1)
            {
                var lch = pos * 2 + 1;
                var rch = pos * 2 + 2;
                if (rch < heap.Count - 1 && cmp(heap[rch], heap[lch]) < 0) lch = rch;
                if (cmp(heap[lch], x) >= 0)
                    break;
                heap[pos] = heap[lch];
                pos = lch;
            }
            heap[pos] = x;
            heap.RemoveAt(heap.Count - 1);
            return ret;

        }



        /// <summary>
        ///  優先度付きキューに含まれる最も価値が低い要素を削除せずに返します．
        /// </summary>
        /// <returns>優先度付きキューに含まれる最も価値が低い要素．</returns>
        /// <remarks>この操作は O(1) で実行されます．</remarks>
        public T Peek() { return heap[0]; }

        /// <summary>
        /// 優先度付きキュー内の要素の数を取得します．
        /// </summary>
        /// <returns>優先度付キュー内にある要素の数</returns>
        /// <remarks>最悪計算量 O(1) で実行されます．</remarks>
        public int Count { get { return heap.Count; } }
        /// <summary>
        /// 優先度付きキュー内に要素が存在するかどうかを O(1) で判定します．
        /// </summary>
        /// <returns>優先度付キュー内にある要素が存在するならば true，そうでなければ　false．</returns>
        /// <remarks>この操作は O(1) で実行されます．</remarks>
        public bool Any() { return heap.Count > 0; }

        /// <summary>
        /// 優先度付きキューに含まれる要素を昇順に並べて返します．
        /// </summary>
        /// <remarks>この操作は計算量 O(N log N)で実行されます．</remarks>
        public T[] Items
        {
            get
            {
                var ret = heap.ToArray();
                Array.Sort(ret, cmp);
                return ret;
            }
        }
    }
    #endregion
}

/// <summary>
/// SEGTREEは1-BASE運用でございます
/// よろしくおねがいします
/// あと絶対コンストラクタ使ってね
/// </summary>
/// <typeparam name="T"></typeparam>
class Segtree<T>
{
    int n;//高さ
    T[] tree;//本体
    Func<T, T, T> f;//更新関数。a -> b -> ab使ったなにか
    T exnum;//初期値
    int count;
    /// <summary>
    /// !!!WARNING!!! 1-BASEです。
    /// </summary>
    /// <param name="m">要素の数の最大値。200001とか入れておくとよい</param>
    /// <param name="f">２引数の関数</param>
    /// <param name="ex">葉に書いてある値の初期値。fの関数に影響を与えない数値、零元とかにしておくべき。バグり散らかす。</param>
    public Segtree(int m, Func<T, T, T> f, T ex)
    {
        this.count = 0;
        this.f = f;
        this.exnum = ex;
        n = 1;
        while (n < m) n <<= 1;

        tree = new T[(n << 1) - 1];
        for (int i = 0; i < tree.Length; i++) tree[i] = ex;
    }
    public Segtree(int m, T ini, Func<T, T, T> f, T ex) : this(m, f, ex)
    {
        this.count = 0;
        for (int i = 0; i < m; ++i) tree[i + n - 1] = ini;
        all_update();
    }

    /// <summary>
    /// j番目の値をxにする。計算し直さないので、
    /// 入れ替えた後はall_update();を使おう
    /// </summary>
    /// <param name="j">番目</param>
    /// <param name="x">更新後の値</param>
    public void assign_without_update(int j, T x)
    {
        tree[j + n - 1] = x;
    }
    /// <summary>
    /// j番目の値をxにする。計算し直すので、ちょっと計算時間がかかる
    /// </summary>
    /// <param name="j">番目</param>
    /// <param name="x">更新後の値</param>
    public void update(int j, T x)//j番目をxにする
    {
        int i = j + n - 1;
        tree[i] = x;
        while (i > 0)
        {
            i = (i - 1) >> 1;
            tree[i] = f(tree[(i << 1) + 1], tree[(i << 1) + 2]);
        }
        this.count++;
    }

    /// <summary>
    /// 木を全部計算し直す。多分NlogN。違うかも知れないから
    /// よかったら教えて
    /// </summary>
    public void all_update()
    {
        for (int i = n - 2; i >= 0; i--)
            tree[i] = f(tree[(i << 1) + 1], tree[(i << 1) + 2]);
    }
    public T look(int i) { return tree[i + n - 1]; }

    /// <summary>
    /// j番目を消す。
    /// </summary>
    /// <param name="j"></param>
    public void delete(int j)
    {
        int i = j + n - 1;
        tree[i] = exnum;
        int moved = 0;

        while (true)
        {
            tree[i + 1] = tree[i];
            T check = tree[i];
            moved++;
            if (moved + j + 2 > count)
            {
                break;
            }

        }
        all_update();
    }


    // [s, t)
    /// <summary>
    /// s番目からt - 1 番目までの結果を返す。t番目は含まない。
    /// これも当然のように1-BASE.
    /// </summary>
    /// <param name="s"></param>
    /// <param name="t"></param>
    /// <returns></returns>
    public T run(int s, int t) { return query(s, t, 0, 0, n); }
    T query(int s, int t, int k, int l, int r)
    {
        if (r <= s || t <= l) return exnum;
        if (s <= l && r <= t) return tree[k];

        return f(query(s, t, (k << 1) + 1, l, (l + r) >> 1), query(s, t, (k + 1) << 1, (l + r) >> 1, r));
    }
}

public class pair<T>
{
    public T A;
    public T B;
    public pair() { }
    public pair(T A, T B)
    {
        this.A = A;
        this.B = B;
    }

}

public class chouten
{
    public int N;
    public List<int> node;

    public chouten(int n)
    {
        this.N = n;
        this.node = new List<int>();
    }

}


public class ab
{
    public int a, b;

    public ab(int a, int b)
    {
        this.a = a;
        this.b = b;
    }

}

public class ABC
{
    //          long[] sp = Console.ReadLine().Split().Select(long .Parse).ToArray();
    //          int[] sp = Console.ReadLine().Split().Select(int.Parse).ToArray();
    //          int N =  int.Parse(Console.ReadLine());
    //CompLib.Collections.PriorityQueue<?>

    //System.Collections.Generic.SortedList<>

    //文字列比較のcomparer
    //StringComparer.OrdinalIgnoreCase


    public static void Main()
    {
        string N = Console.ReadLine();
        int wa = 0;
        for (int i = 0; i < N.Length; i++)
        {
            int d = int.Parse(N[i].ToString());
            wa += d;

        }
        string output = "Yes";
        if (wa % 9 == 0)
        {

        }
        else
        {
            output = "No";
        }
        Console.WriteLine(output);

    }


}



Measured memory_bytes: 32728