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

namespace AIZUproject07
{
    class Program
    {
        //static string T;
        /*static void Main()
        {
            int count = 0;
            bool flag = false;
            string In = Console.ReadLine();
            string[] s = Console.ReadLine().Split();
            int[] aa = s.Select(int.Parse).ToArray();
            while (true)
            {
                for (int i = 0; i < aa.Length; i++)
                {
                    if (aa[i] % 2 != 0)
                    {
                        flag = true;
                    }
                    
                }
                aa = aa.Select(n => n / 2).ToArray();
                if (flag == true) break;
                count++;
            }
            Console.WriteLine(count);
        }*/
        /*static void Main()
        {
            int sum = 0;
            int count = 0;
            string A = Console.ReadLine();
            string B = Console.ReadLine();
            string C = Console.ReadLine();
            string D = Console.ReadLine();
            int AA = int.Parse(A);
            int BB = int.Parse(B);
            int CC = int.Parse(C);
            int DD = int.Parse(D);
            for(int i = 0;i<=AA;i++)
            {
                for (int j=0;j<=BB;j++)
                {
                    for (int k =0;k<=CC;k++)
                    {
                        sum = i * 500 + j * 100 + k * 50;
                        if (sum == DD) count++;
                    }
                }
            }
            Console.WriteLine(count);
        }*/
        /*static void Main()
        {
            int ans1 = 0;
            int ans2 = 0;
            string[] s = Console.ReadLine().Split();
            int[] intArray = s.Select(int.Parse).ToArray();
            for (int i = 1;i<=intArray[0];i++)
            {
                ans1 = 0;
                if (i >= 10 && i <100)
                {
                    var aaa = i % 10;
                    var bbb = i / 10;
                    ans1 = aaa + bbb;
                    if (intArray[1] <= ans1 && ans1 <= intArray[2])
                    {
                        ans2 += i;
                    }
                }
                if (i >= 100 && i<1000)
                {
                    var aaa = i % 10;
                    var bbb = i / 10;
                    var ccc = bbb % 10;
                    var ddd = bbb / 10;
                    ans1 = aaa + ccc + ddd;
                    if (intArray[1] <= ans1 && ans1 <= intArray[2])
                    {
                        ans2 += i;
                    }
                }
                if (i >= 1000 && i <10000)
                {
                    var aaa = i % 10;//4
                    var bbb = i / 10;
                    var ccc = bbb % 10;//3
                    var ddd = bbb / 10;
                    var eee = ddd % 10;//2
                    var fff = ddd / 10;//1
                    ans1 = aaa + ccc + eee + fff;
                    if (intArray[1] <= ans1 && ans1 <= intArray[2])
                    {
                        ans2 += i;
                    }
                }
                if (i == 10000)
                {
                    ans1 = 1;
                    if (intArray[1] <= ans1 && ans1 <= intArray[2])
                    {
                        ans2 += i;
                    }
                }
                if (i < 10)
                {
                    ans1 = i;
                    if (intArray[1] <= ans1 && ans1 <= intArray[2])
                    {
                        ans2 += i;
                    }
                }
            }
            Console.WriteLine(ans2);
        }*/
        /*static void Main()
        {
            int sum = 0;
            bool test = false;
            string[] aa = Console.ReadLine().Split();
            int N = int.Parse(aa[0]);
            int Y = int.Parse(aa[1]);
            int Yukichi = Y / 10000;
            int Ichiyo = Y / 5000;
            int Hideyo = Y / 1000;
            int x = 0;
            int y = 0;
            int z = 0;
            for (int i = 0;i<=Yukichi;i++)
            {
                for (int j =0;j<=Ichiyo;j++)
                {
                    for (int k =0;k<=Hideyo;k++)
                    {
                        sum = 10000 * i + 5000 * j + 1000 * k;
                        if (sum == Y && i+j+k < N)
                        {
                            x = i;
                            y = j;
                            z = k;
                            //Console.WriteLine(i + " " + j + " " + k);
                            test = true;
                        }
                    }
                }
            }
            if (test == true)
            {
                Console.WriteLine(x + " " + y + " " + z);
            }
            if (test == false)
            {
                Console.WriteLine("-1 -1 -1");
            }
        }*/
        /*static void Main()
        {
            string[] aa = Console.ReadLine().Split();
            int N = int.Parse(aa[0]);
            int Y = int.Parse(aa[1]);
            int X = 0;
            int Z = 0;
            int b = 0;
            int d = 0;
            X = Y / 10000;
            var a = Y - (X*10000);
            if (a != 0 || Y < 10000)
            {
                b = a / 5000;
                var cc = a - (b * 5000);
                if (cc != 0 || a < 5000)
                {
                    d = cc / 1000;
                    var gg = cc - (d * 1000);
                    if (gg != 0 ||  cc<1000)
                    {
                        Console.WriteLine("-1 -1 -1");
                    }
                    else if (X + b + d <= N)
                    {
                        Console.WriteLine(X + " " + b + " " + d);
                    }
                    else if (X + b + d > N)
                    {
                        Console.WriteLine("-1 -1 -1");
                    }
                }
                else if (X + b <= N)
                {
                    Console.WriteLine(X +" "+ b +" "+"0");
                }
                else if (X + b > N)
                {
                    Console.WriteLine("-1 -1 -1");
                }
            }
            else if (X <= N)
            {
                Console.WriteLine(X +" "+0+" "+0);
            }
            else if (X>N)
            {
                Console.WriteLine("-1 -1 -1");
            }
        }*/
        /*static void Main()
        {
            string s = Console.ReadLine();

            var Ans = s.Replace("eraser", "").Replace("dreamer", "").Replace("dreamer", "").Replace("erase", "").ToString();
            if (Ans == null) Console.WriteLine("YES");
            else Console.WriteLine("NO");*/

        //List<string> str = new List<string>(); || s.Substring(5, 1) == ""
        //string NN = new string(s); || s.Substring(5,1) == ""
        /*while (true) { 
            while (true)
            {
                    if (s.StartsWith("dream") && (s.Substring(5,2) != "er" ))
                    {
                        count++;
                        var f = s.Remove(0, 5);
                        s = f;
                        break;
                    }
                    if (s.StartsWith("dreamer"))
                    {

                        var n = s.Remove(0, 7);
                        s = n;
                        break;
                    }
                    if (s.StartsWith("erase") || (s.Substring(5,1) != "r" ))
                    {
                        count2++;
                        var f1 = s.Remove(0, 5);
                        s = f1;
                        break;
                    }
                    if (s.StartsWith("eraser"))
                    {

                        var f2 = s.Remove(0, 6);
                        s = f2;
                        break;
                    }
                else
                {
                    tt = true;
                    break;
                }
            }
            if (s.Length == 0)
            {
                Console.WriteLine("YES");
                break;
            }
            if (tt)
            {
                Console.WriteLine("NO");
                break;
            }
        }*/
        //Console.WriteLine(count+","+count2);
        //}

        //86C
        /*static void Main()
        {
            /*string aa = Console.ReadLine();
            List<int[]> nn = new List<int[]>();
            for (int i = 0;i<aa.Length;i++)
            {
                string[] str = Console.ReadLine().Split();
                int[] intstr = str.Select(int.Parse).ToArray();
                nn.Add(intstr);
            }
            var a1 = Console.ReadLine().Split().Select(int.Parse).ToArray();
            var num = a1[0];
            var list = new List<int[]>(num);
            for (int i=0;i<num;i++)
            {

            }
        }*/
        /*static void Main(string[] args)
        {
            var input = Console.ReadLine().Split(' ');
            var array = input.Select(int.Parse).ToArray();
            int num = array[0] * 100 + array[1] * 10 + array[2] * 1;
            if (num % 4 == 0)
            {
                Console.WriteLine("YES");
            }
            else
            {
                Console.WriteLine("NO");
            }
        }*/
        /*static void Main()
        {
            var input = Console.ReadLine();
            var a = Console.ReadLine();
            int N = int.Parse(input);
            int A = int.Parse(a);
            bool flag = false;
            for (int i = 0;i <= A;i++ )
            {
                var Ans = N - i;
                if (Ans % 500 == 0)
                {
                    Console.WriteLine("Yes");
                    flag = true;
                    break;
                }
            }
            if (flag == false)
            {
                Console.WriteLine("No");
            }

        }*/
        /*static void Main()
        {
            var a = Console.ReadLine().Split();
            double[] integer = a.Select(double.Parse).ToArray();
            double ans = (integer[0] + integer[1]) / 2;
            Console.WriteLine(Math.Ceiling(ans));
        }*/
        /*static void Main()
        {
            int count = 0;
            string str = Console.ReadLine();
            //var cross = str.Select(n => n != '×');
            //var circle = str.Select(n => n != 'o');
            //Console.WriteLine(cross);
            //Console.WriteLine(circle);
            /*Console.WriteLine(str.Length);
            while (true)
            {
                Match match1 = Regex.Match(str, "o");
                if (match1 != null)
                {
                    count++;
                }
                str = str.Substring(match1.Index+1, str.Length);
                if (match1.Index == str.Length)
                {
                    break;
                }
            }
            var Ans = 700 + count * 100;
            Console.WriteLine(Ans);*/
        //Console.WriteLine(match.Value);
        /*or (int i =0;i<str.Length;i++)
        {
            if (Regex.Match(str[i], "o"))
            {

            }
        }
        count = str.Length - str.Replace("o", "").Length;
        var Ans = 700 + count * 100;
        Console.WriteLine(Ans);
        }*/
        /*static void Main()
        {
            var str = Console.ReadLine();
            var Ans = str.Replace("2017","2018");
            Console.WriteLine(Ans);
        }*/
        /*static void Main()
        {
            var str = Console.ReadLine();
            //str.Substring(0, 1) +
            Console.WriteLine(str.Substring(0, 1) + (str.Length-2) + str.Substring(str.Length-1));
        }*/
        //82B
        /*static void Main()
        {
            var s = Console.ReadLine();
            var t = Console.ReadLine();
            char[] S = s.ToArray();
            char[] T = t.ToArray();
            Array.Sort(S);
            Array.Sort(T);Array.Reverse(T);
            string ss = new string(S);
            string ts = new string(T);
            if (ss.CompareTo(ts) < 0)
            {
                Console.WriteLine("Yes");
            }
            else
            {
                Console.WriteLine("No");
            }*/

        //sに関してソート
        /*for (int i = 0; i < s.Length; i++)
        {

        }*/
        //var hoge = s.OrderByDescending((x) => x.Value);
        /*List<int> array = new List<int>();
        int[] rank = new int[s.Length];
        for (int i = 0; i < s.Length; i++)
        {
            rank[i] = 0;
        }
        for (int i = 0; i < s.Length; i++)
        {
            for (int j = 0; j < s.Length; j++)
            {
                if (s[i] > s[j])
                {
                    rank[i]++;
                }
            }
        }
        for (int i=0;i<s.Length;i++)
        {
            for (int j =0;j<s.Length;j++)
            {
                if (i == rank[j])
                {
                    array.Add(s[i]);
                }
            }
        }
        for (int i = 0; i < s.Length; i++)
        {
            Console.Write(array[i]);
        }

    }*/
        /*static void Main()
        {
            int count;
            int temp = 0;
            var N = int.Parse(Console.ReadLine());
            List<int> aa = new List<int>();
            for (int i = 1; i <= N; i++)
            {
                count = 0;
                temp = i;
                while (true)
                {
                    var Ans = temp / 2;
                    var Ans2 = temp % 2;
                    if (Ans2 == 0)
                    {
                        count++;
                        temp = Ans;
                    }
                    else
                    {
                        break;
                    }
                }
                aa.Add(count);
            }
            //Program program = new Program();
            //program.Max(aa, temp);
            var max = aa.IndexOf(aa.Max());
            Console.WriteLine(max+1);

        }
        public void Max(List<int> array,int num)
        {
            var Ans3 = array.Max();
        }*/
        /*static void Main()
        {
            List<int> array = new List<int>();
            var N = Console.ReadLine();
            int[] A = Console.ReadLine().Split().Select(int.Parse).ToArray();
            for (int i = 0;i<A.Length;i++)
            {
                for (int j = 0; j< A.Length; j++)
                {
                    var ans = A[i] - A[j];
                    if (ans < 0)
                    {
                         ans = Math.Abs(ans);
                    }
                    //Console.Write(ans);
                    array.Add(ans);
                }
                //Console.WriteLine();
            }
            Console.WriteLine(array.Max());
        }*/
        /*static void Main()
        {
            var N = Console.ReadLine();
            int[] temperture = Console.ReadLine().Split().Select(int.Parse).ToArray();
            int[] height = Console.ReadLine().Split().Select(int.Parse).ToArray();
            int T = temperture[0];
            int A = temperture[1];
            List<double> aa = new List<double>();
            List<double> bb = new List<double>();
            for (int i = 0;i<height.Length;i++)
            {
                var temp = T - height[i] * 0.006;
                aa.Add(temp);
            }
            for (int i =0;i<height.Length;i++)
            {
                var temp = A - aa[i];
                if (temp < 0)
                {
                    temp = Math.Abs(temp);
                }
                bb.Add(temp);
            }
            Console.WriteLine(bb.IndexOf(bb.Min())+1);
        }*/
        /*static void Main()
        {
            string a = Console.ReadLine();
            char[] charArray = a.ToArray();
            List<char> aa = new List<char>();
            for (int i = 0;i<charArray.Length;i++)
            {
                if ((i+1)%2 == 1)
                {
                    aa.Add(charArray[i]);
                }
            }
            var str = string.Join("",aa);
            Console.WriteLine(str);
        }*/
        //053B
        /*static void Main()
        {
            var str = Console.ReadLine();
            var start = str.IndexOf("A");
            var goal = str.IndexOf("Z",start);
            string temp = new string(str.Substring(goal).ToArray());
            int goalpoint = 0;
            List<int> kk = new List<int>();
            while (true)
            {
                if (temp.Contains("Z"))
                {
                    goalpoint = temp.IndexOf("Z") +1;
                    temp = temp.Replace("Z", "");
                    
                }
                if (temp.Contains("Z") == false)
                {
                    break;
                }
                if(temp.Contains("Z"))
                {
                    Console.WriteLine();
                }
            }
            for (int i = 0;i<temp.Length;i++)
            {
                if (temp[i] == 'Z')
                {
                    goalpoint = i;
                }
                
            }
            var ans = str.Substring(start, goal-start).Length + 1 + goalpoint;
            Console.WriteLine(ans);
        }*/
        //095B
        /*static void Main()
        {
            var a = Console.ReadLine().Split().Select(int.Parse).ToArray();
            int N = a[0];
            int X = a[1];
            List<int> listarray = new List<int>();
            int Ans = 0;
            for (int i =0;i < N;i++)
            {
                var temp = Console.ReadLine();
                int temp1 = int.Parse(temp);
                listarray.Add(temp1);
            }
            for (int i =0;i< N;i++)
            {
                X = X - listarray[i];
                if (X >= 0)
                {
                    Ans++;
                }
            }
            if (X > 0)
            {
                while (true)
                {
                    X = X - listarray.Min();
                    if (X < 0)
                    {
                        break;
                    }
                    Ans++;
                }
            }
            Console.WriteLine(Ans);
        }*/
        //105B
        /*static void Main()
        {
            int dunats = 7;
            int cake = 4;
            int sum = 0;
            bool flag = false;
            int N = int.Parse(Console.ReadLine());
            if (N > 3)
            {
                for (int i = 0; i <= N / cake; i++)
                {
                    for (int j=0; j<=N/dunats;j++)
                    {
                        sum = dunats * j + cake * i;
                        if (sum == N) {
                            flag = true;
                        }
                        if (flag == true)
                        {
                            break;
                        }
                    }
                    if (flag == true)
                    {
                        break;
                    }
                }
            }
            if (flag == true) { Console.WriteLine("Yes"); }
            else { Console.WriteLine("No"); }
        }*/
        //004A
        /*static void Main()
        {
            List<double> Ans = new List<double>();
            List<int[]> array = new List<int[]>();
            int N = int.Parse(Console.ReadLine());
            for (int i = 0; i < N; i++)
            {
                int[] aa = Console.ReadLine().Split().Select(int.Parse).ToArray();
                array.Add(aa);
            }
            for (int i=0;i<N;i++)
            {
                for (int j = 0;j<N;j++)
                {
                    var X = array[i][0] - array[j][0];
                    var Y = array[i][1] - array[j][1];
                    var resultX = Math.Pow(X, 2);
                    var resultY = Math.Pow(Y, 2);
                    var ans = Math.Sqrt(resultX + resultY);
                    Ans.Add(ans);
                }
            }
            var finalresult = Ans.Max();
            Console.WriteLine(finalresult);
        }*/
        //51B
        /*static void Main()
        {
            int count = 0;
            int[] input = Console.ReadLine().Split().Select(int.Parse).ToArray();
            int K = input[0];
            int S = input[1];
            for (int x =0;x<= K;x++)
            {
                for (int y = 0; y <= K; y++) 
                {
                     var z = S - x - y;
                    if ( 0 <= z && z <= K)
                    {
                        count++;
                    }
                }
            }
            Console.WriteLine(count);
        }*/
        //80B
        /*static void Main()
        {
            int Ans = 0;
            string x = Console.ReadLine();
            int X = int.Parse(x);
            for (int i =0;i<x.Length;i++)
            {
                var temp = Convert.ToInt32(x[i].ToString());
                Ans += temp;
            }
            if (X % Ans == 0)
            {
                Console.WriteLine("Yes");
            }
            else
            {
                Console.WriteLine("No");
            }
        }*/
        //90B
        /*static void Main()
        {
            int[] input = Console.ReadLine().Split().Select(int.Parse).ToArray();
            int A = input[0];
            int B = input[1];
            int aaa = 0;
            int count = 1;
            int ko = 0;
            string ans ="";
            StringBuilder sb = new StringBuilder();
            while(true)
            { 
                string X = A.ToString();
                count = 1;
                ans = "";
                //Console.WriteLine(X[X.Length - count]);
                while (true)
                {
                   
                    //sb = null;
                    sb.Append(X[X.Length - count]);
                    if (X.Length - count  == 0)
                    {
                        ans = sb.ToString();
                        break;
                    }
                    count++;
                }
                sb.Remove(0,X.Length);
                aaa = int.Parse(ans);
                //Console.WriteLine(aaa);
                if (A == aaa)
                {
                    ko++;
                }

                if (A == B)
                {
                    break;
                }
                A++;
            }
            Console.WriteLine(ko);
        }*/
        //25A
        /*static void Main()
        {
            int ansA = 0;
            int ansB = 0;
            int N = int.Parse(Console.ReadLine());
            List<int> Ans = new List<int>();

            for (int A = 1;A<N;A++)
            {
                int B = N - A;
                    List<int> la = new List<int>();
                    List<int> lb = new List<int>();
                    ansA = 0;
                    ansB = 0;
                    string a = A.ToString();
                    string b = B.ToString();
                    for (int i =0;i<a.Length;i++)
                    {
                        char ca = a[i];
                        int intca = Convert.ToInt32(ca.ToString());
                        la.Add(intca);
                    }
                    for (int i=0;i<b.Length;i++)
                    {
                        char cb = b[i];
                        int intcb = Convert.ToInt32(cb.ToString());
                        lb.Add(intcb);
                    }
                    foreach(int n in la)
                    {
                        ansA += n;
                    }
                    foreach (int n in lb)
                    {
                        ansB += n;
                    }
                    Ans.Add(ansA + ansB);
            }
            Console.WriteLine(Ans.Min());
        }*/
        //67B
        /*static void Main()
        {
            int Ans = 0;
            List<int> array = new List<int>();
            int[] input = Console.ReadLine().Split().Select(int.Parse).ToArray();
            int N = input[0];
            int K = input[1];
            int[] length = Console.ReadLine().Split().Select(int.Parse).ToArray();
            //int[] newone = new int[length.Length];
            Array.Sort(length);
            Array.Reverse(length);
            for (int i = 0;i<K;i++)
            {
                array.Add(length[i]);
                Ans += length[i];
            }
            Console.WriteLine(Ans);
        }*/
        //42B
        /*static void Main()
        {
            
            int[] input = Console.ReadLine().Split().Select(int.Parse).ToArray();
            int N = input[0];
            int L = input[1];
            string[] str = new string[N];
            for (int i=0;i<N;i++)
            {
                var a = Console.ReadLine();
                str[i] = a;
            }
            StringComparer cmp = StringComparer.OrdinalIgnoreCase;
            Array.Sort(str,cmp);
            List<string> Ans = new List<string>();
            for (int i = 0;i<N;i++)
            {
                 Ans.Add(string.Concat(str[i]));
            }
            StringBuilder sb = new StringBuilder();
            for (int i = 0;i<N;i++)
            {
                sb.Append(Ans[i]);
                sb.Append(string.Concat(str[i]));
            }
            Console.WriteLine(sb);
        }*/
        //27A
        /*static void Main()
        {
            int count = 0;
            int[] input = Console.ReadLine().Split().Select(int.Parse).ToArray();
            int N = input[0];
            int x = input[1];
            var a = Console.ReadLine().Split().Select(int.Parse).ToArray();
            
            foreach (int i in a.OrderBy(nn => nn))
            {
                x -= i;
                if (x >= 0)
                {
                    count++;
                }
                if(x < 0)
                {
                    break;
                }
            }
            if (x > 0)
            {
                count--;
            }
            Console.WriteLine(count);
        }*/
        //12A
        /*static void Main()
        {
            int Ans = 0;
            int N = int.Parse(Console.ReadLine());
            int[] Aarray = Console.ReadLine().Split().Select(int.Parse).ToArray();

            Array.Sort(Aarray);
            Array.Reverse(Aarray);
            Array.Clear(Aarray, 0, N);
            for (int i = N;i< 2*N; i++)
            {
                Ans += Aarray[i];
            }
            Console.WriteLine(Ans);

        }*/
        /*static void Main()
        {
            int o = 0;
            string Ans;
            string input = Console.ReadLine();
            string alphabet = "abcdefghijklmnopqrstuvwxyz";
            for (int i = 0;i< input.Length;i++)
            {
                char temp = input[i];
                string ans =  string.Join("", temp);
                if (alphabet.Contains(ans))
                {
                     alphabet =  alphabet.Replace(ans,"");
                     //o  = alphabet.Length - alphabet.Replace(ans, "").Length;
                }
                
            }
            if (alphabet == "")
            {
                Console.WriteLine("None");
            }
            else
            {
                Console.WriteLine(alphabet.Min());
                //alphabet.Min()
            }
        }*/
        //61B
        /*static void Main()
        {
            int[] input = Console.ReadLine().Split().Select(int.Parse).ToArray();
            int N = input[0];
            int M = input[1];
            List<int[]> map = new List<int[]>();
            for (int i =0;i<M;i++)
            {
                int[] road = Console.ReadLine().Split().Select(int.Parse).ToArray();
                map.Add(road);
            }
            List<int> ans = new List<int>();
            for (int i = 0;i< N;i++)
            {
                ans.Add(0);
            }
            for (int i = 0; i<N;i++)
            {
                var ff = i+1;
                foreach (int[] n in map)
                {
                    for (int j = 0; j < 2; j++)
                    {
                        if (n[j] == ff)
                        {
                            ans[i]++;
                        }
                    }
                }
            }
            for (int i=0;i<N; i++)
            {
                Console.WriteLine(ans[i]);
            }
        }*/
        //47B
        /*static void Main()
        {
            int[] input = Console.ReadLine().Split().Select(int.Parse).ToArray();
            int X = input[0];
            int Y = input[1];
            int N = input[2];
            int[,]  map = new int[X+1,Y+1];
            for (int i =0;i<N;i++)
            {
                int[] input2 = Console.ReadLine().Split().Select(int.Parse).ToArray();
                int x = input2[0];
                int y = input2[1];
                int a = input2[2];
                switch (a)
                {
                    case 1:
                        for (int ty =0;ty<Y;ty++) {
                            for (int j = 0; j <x; j++)
                            {
                                map[j, ty] += 1;
                            }
                        }
                        break;
                    case 2:
                        for (int ty = 0; ty < Y; ty++) {
                            for (int j = x; j < X; j++)
                            {
                                map[j, ty] += 1;
                            }
                        }
                        break;
                    case 3:
                        for (int tx = 0; tx < X; tx++)
                        {
                            for (int j = 0; j < y; j++)
                            {
                                map[tx, j] += 1;
                            }
                        }
                        break;
                    case 4:
                        for (int tx = 0; tx < X; tx++)
                        {
                            for (int j = y; j < Y; j++)
                            {
                                map[tx, j] += 1;
                            }
                        }
                        break;
                }
            }
            int count = 0;
            for (int i = 0;i<X;i++)
            {
                for (int j = 0;j<Y;j++)
                {
                    if (map[i,j] == 0)
                    {
                        count++;
                    }
                }
            }
            Console.WriteLine(count);
        }*/
        //91B
        /*static void Main()
        {
            bool ji = false;
            int N = int.Parse(Console.ReadLine());
            List<string> bluewords = new List<string>();
            List<string> redwords = new List<string>();
            for (int i = 0; i < N;i++)
            {
                var temp = Console.ReadLine();
                bluewords.Add(temp);
            }
            int M = int.Parse(Console.ReadLine());
            for (int i = 0; i < M; i++)
            {
                var temp = Console.ReadLine();
                redwords.Add(temp);
            }
            List<KeyValuePair<int,string>> countBlue = new List<KeyValuePair<int, string>>();
            int a = 0;
            foreach (string n in bluewords)
            {
                foreach (string l in bluewords)
                {
                    if (n == l)
                    {
                        a++;
                    }
                }
                KeyValuePair<int, string> tempKey = new KeyValuePair<int, string>(a,n);
                countBlue.Add(tempKey);
                a = 0;
            }
            countBlue.Sort((w, x) => x.Key - w.Key);

            List<KeyValuePair<int, string>> countRed = new List<KeyValuePair<int, string>>();
            int b = 0;
            foreach (string n in redwords)
            {
                foreach (string l in redwords)
                {
                    if (n == l)
                    {
                        b++;
                    }
                }
                KeyValuePair<int, string> tempKey1 = new KeyValuePair<int, string>(b, n);
                countRed.Add(tempKey1);
                b = 0;
            }
            countRed.Sort((w, x) => x.Key - w.Key);

            List<int> ans = new List<int>();
            int countt = 0;
            foreach (var blue in countBlue)
            {
                foreach (var red in countRed)
                {
                    countt = 0;
                    var andss = new List<bool>(countRed.Select(d => d.Value == blue.Value));
                    foreach (var tt in andss)
                    {
                        var ee = tt;
                        if (ee == false)
                        {
                            countt++;
                        }
                    }
                    if (blue.Value == red.Value)
                    {
                        var Ans = blue.Key - red.Key;
                        ans.Add(Ans);
                        break;
                    }
                    else if(countt == andss.Count)
                    {
                        var Ans = blue.Key;
                        ans.Add(Ans);
                    }
                }
            }
            if (ans.Max() <= 0)
            {
                Console.WriteLine("0");
            }
            else
            {
                Console.WriteLine(ans.Max());
            }
        }*/
        //130コンテスト
        /*static void Main()
        {
            int[] input = Console.ReadLine().Split().Select(int.Parse).ToArray();
            int X = input[0];
            int A = input[1];
            if (X < A)
            {
                Console.WriteLine("0");
            }
            else
            {
                Console.WriteLine("10");
            }
        }*/
        //130B
        /*static void Main()
        {
            int[] input = Console.ReadLine().Split().Select(int.Parse).ToArray();
            int[] Xarray = Console.ReadLine().Split().Select(int.Parse).ToArray();
            int N = input[0];
            int X = input[1];
            List<int> Ans = new List<int>();
            List<int> Ans1 = new List<int>();
            int ans = 0;
            Ans.Add(ans);
            for (int i = 0; i < Xarray.Length; i++)
            {
                ans += Xarray[i];
                Ans.Add(ans);
            }
            foreach (int a in Ans)
            {
                if (a <= X)
                {
                    Ans1.Add(a);
                }
            }
            Console.WriteLine(Ans1.Count);
        }*/
        //130C
        /*static void Main()
        {
            double[] input = Console.ReadLine().Split().Select(double.Parse).ToArray();
            double W = input[0];
            double H = input[1];
            double x = input[2];
            double y = input[3];
            double temp1 = W * H/2;
            var ans = temp1;
            int ans2 = 0;
            if (x == W/2 && y== H/2)
            {
                ans2 = 1;
            }
            else
            {
                ans2 = 0;
            }
            Console.WriteLine(ans+" "+ans2);
        }*/
        //130D
        /*static void Main()
        {
            int[] input = Console.ReadLine().Split().Select(int.Parse).ToArray();
            int N = input[0];
            int K = input[1];
            int[] Aarray = Console.ReadLine().Split().Select(int.Parse).ToArray();
            int Answer = 0;
            int AnsCount = 0;
            for (int i = 0;i< N;i++)
            {
                Answer += Aarray[i];
                for (int j = i+1;j<N;j++)
                {
                    Answer += Aarray[j];
                    if (Answer >= K)
                    {
                        AnsCount++;

                        AnsCount+=Aarray.Length - j;
                        //AnsCount += N - Answer + 1;
                        break;
                    }
                }
                Answer = 0;
            }
            Console.WriteLine(AnsCount);
        }*/
        //129B
        static void Main()
        {
            int N = int.Parse(Console.ReadLine());
            int[] array = Console.ReadLine().Split().Select(int.Parse).ToArray();
            int Answer = 0;
            int Answer2 = 0;
            List<int> Ans = new List<int>();
            for (int i=0;i<array.Length;i++)
            {
                Answer += array[i];
                for (int j=i+1;j<array.Length;j++)
                {
                    Answer2 += array[j];
                }
                Ans.Add(Math.Abs(Answer - Answer2));
                Answer2 = 0;
            }
            Console.WriteLine(Ans.Min());

        }
    }
}


Measured memory_bytes: 13396