Problem: Vitya is studying in the third grade. During the last math lesson all the pupils wrote on arithmetic quiz. Vitya is a clever boy, so he managed to finish all the tasks pretty fast and Oksana Fillipovna gave him a new one, that is much harder.

Let's denote a flip operation of an integer as follows: number is considered in decimal notation and then reverted. If there are any leading zeroes afterwards, they are thrown away. For example, if we flip 123 the result is the integer 321, but flipping 130 we obtain 31, and by flipping 31 we come to 13.

Oksana Fillipovna picked some number a without leading zeroes, and flipped it to get number ar. Then she summed a and ar, and told Vitya the resulting value n. His goal is to find any valid a.

As Oksana Fillipovna picked some small integers as a and ar, Vitya managed to find the answer pretty fast and became interested in finding some general algorithm to deal with this problem. Now, he wants you to write the program that for given n finds any a without leading zeroes, such that a + ar = n or determine that such a doesn't exist.

Input

The first line of the input contains a single integer n (1 ≤ n ≤ 10100 000).

Output

If there is no such positive integer a without leading zeroes that a + ar = n then print 0. Otherwise, print any valid a. If there are many possible answers, you are allowed to pick any.

Examples

Input

4


Output

2


Input

11


Output

10


Input

5


Output

0


Input

33


Output

21

Note

In the first sample 4 = 2 + 2, a = 2 is the only possibility.

In the second sample 11 = 10 + 1, a = 10 — the only valid solution. Note, that a = 01 is incorrect, because a can't have leading zeroes.

It's easy to check that there is no suitable a in the third sample.

In the fourth sample 33 = 30 + 3 = 12 + 21, so there are three possibilities for a: a = 30, a = 12, a = 21. Any of these is considered to be correct answer.

Solution (in JAVA):

Solution:
import java.util.*; 
public class ProblemD2 {
        private static String ans;
        private static void pretreat(StringBuilder s){
                for(int i = 0; i < s.length(); ++i){
                        if(s.charAt(i)  != '0'){
                                s = s.delete(0, i);
                                break;
                        }
                }
                s.insert(0,'0');
        }
        private static void solve(StringBuilder s){
                pretreat(s);
                if(caseLittle(s)){
                        return ;
                }
                else if(caseOne(s)){
                        return;
                }
                else if(caseOthers(s)){
                        return;
                }
                else{
                        ans = "0";
                }
        }
        private static boolean caseLittle(StringBuilder s){
                if(s.length() <= 2){
                        int n= Integer.parseInt(s.toString());
                        if((n&1) == 0){
                                ans = "" + n / 2;
                        }
                        else{
                                ans = "0";
                        }
                        return true;
                }
                return false;
        }
        private static boolean caseOne(StringBuilder s){
                if(s.charAt(1) == '1'){
                        return constructAns(s,true);
                }
                return false;
        }
        private static boolean caseOthers(StringBuilder s){
                return constructAns(s,false);
        }
        private static boolean constructAns(StringBuilder s,boolean FirstBitHasCarry)
        {
                int n = s.length();
                int front = FirstBitHasCarry ? 2 : 1;
                int rear = n - 1;
                boolean[] carry =new boolean[n+10];
                Arrays.fill(carry, false);
                carry[front - 1] = FirstBitHasCarry;
                for(int l = front; (l<<1) < front + rear; ++l){ //(l<<1)就是l+l,退出循环的条件是l>=r
                        int r = front + rear - l;               //求出r,注意,此时carry[l-1]以及之前的值,carry[r]以及之后的值都是已知的,.
                                                                        //需要求的是carry[l] 和 carry[r-1].
                        if(s.charAt(l) == s.charAt(r)){
                                carry[l] = carry[r];   //如果两位数字相等,说明这两位的加数和进位均相同,直接令carry[l] = carry[r].
                                carry[r - 1] = carry[l - 1];    //同样的,r的进位和l的进位也必定相同,即carry[r-1] = carry[l-1].
                                if(l == r - 1 && carry[l - 1] != carry[r]) //如果l==r-1,但carry[l]与carry[r-1]不同,则直接返回false,但是不能直接比较carry[l]与carry[r-1],
                                        return false;     //因为这时他们是同一个数,只能比较他们本应被赋的值,即carry[l] 用 carry[r]代替,carry[r-1] 用carry[l-1]代替.
                        }
                        else if(s.charAt(l) == s.charAt(r) + 1){
                                if(carry[r])
                                        return false; //如果s[l] == s[r] + 1,那么carry[r]应该为0,carry[l]应该为1,所以如果carry[r]为1,那么必定无解.
                                if(l == r -1 && !carry[l - 1])     //l等于r-1时,仍然比较carry[l] 与 carry[r-1] 本应被赋的值,因为carry[l]本应等于1,所以,carry[l-1]也应该等于1,否则无解.
                                        return false; 
                                carry[l] = true;
                                carry[r - 1] = carry[l - 1]; //因为若满足s[l] == s[r] + 1,则s[r]最大值为8,所以,不存在l位进位,r位不进位的情况,即直接令其相等.
                        }
                        else if(s.charAt(l) + 1 == s.charAt(r)){  
                                //与上一个判定类似,可以自己思考.
                                if(!carry[r])
                                        return false;
                                if(l == r -1 && carry[l - 1])
                                        return false;
                                carry[l] = false;
                                carry[r - 1] = carry[l -1];
                        }
                        else if(s.charAt(l) == '0' && s.charAt(r) == '9'){
                                //这个是s[l] == s[r]+1的一种特殊情况,与其类似,需要注意的是因为carry[r]为0,两个一位数相加时,如果没有来自前一位的进位,
                                //不可能加出来19,所以当s[r]等于9时,carry[r-1]必定为0.又因为carry[l]必定为1,两者注定不相等,所以如果l == r-1,则必定矛盾,即无解.
                                if(carry[r])
                                        return false;
                                if(l == r - 1) 
                                        return false;
                                carry[l] =  true;
                                carry[r - 1] = false;
                        }
                        else if(s.charAt(l) == '9' && s.charAt(r) == '0'){
                                //与上一个判定类似,可以自己思考下.
                                if(!carry[r])
                                        return false;
                                if(l == r -1)
                                        return false;
                                carry[l] = false;
                                carry[r - 1] = true;
                        }
                        else{
                                //如果相差大于1,则无解.
                                return false;
                        }
                }
                //code below is to check
                for(int l = front; l <= rear; ++l){
                        if(s.charAt(l) == '0' && carry[l] && !carry[l - 1] ){
                                return false;
                        }
                        if(s.charAt(l) == '9' && carry[l-1] && !carry[l]){
                                return false;
                        }
                }
                //code below is to construct the ans;
                int[] bit = new int[n + 10];
                for(int l = front; (l<<1) <= front + rear; ++l){
                        int x = s.charAt(l) - '0';
                        int r = front + rear - l;
                        x +=  (carry[l-1] ? 10 : 0) - (carry[l] ? 1 : 0); 
                        if(l == r && (x&1) == 1)
                                return false;
                        bit[r] = (x >> 1);
                        bit[l] =  x - bit[r];
                }
                if(bit[front] == 0)
                        return false;
                StringBuilder sb = new StringBuilder("");
                for(int i = front; i <= rear; ++i){
                        sb.append(Integer.toString(bit[i]));
                }
                ans = sb.toString();
                return true;
        }
        public static void main(String[] args) {
                // TODO Auto-generated method stub
               // test();
                Scanner scan = new Scanner(System.in);
                StringBuilder s = new StringBuilder(scan.nextLine());
                solve(s);
                System.out.print(ans);
               scan.close();
        }
        /* 
         //code below is just for test
        private static void test(){
                  for(int i  = 1 ; i < 1000000; ++i){
                                StringBuilder s = new StringBuilder(Integer.toString(i));
                                solve(s);
                                int x =  myParseInt(ans);
                                if(x !=0 && x+ flip(x)!=i){
                                        System.out.println(i);
                                        System.out.println(ans);
                                }
                  }
                  System.out.println("done");
        }
        private static int flip(int x){
                int ans = 0;
                while(x>0){
                        ans = ans * 10 + x % 10;
                        x /= 10;
                }
                return ans;
        }
        private static int myParseInt(String s){
                int ans = 0;
                for(int i = 0; i < s.length(); ++i){
                        ans = ans*10 + (s.charAt(i) - '0');
                }
                return ans;
        }
         */
}