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 CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
int main() {
  std::string n;
  std::cin >> n;
  int a[100000], b, ans[100000];
  b = n.size();
  for (int i = 0; i < b; i++) {
    a[i] = (int)n[i] - 48;
  }
  bool p[2];
  p[0] = true;
  p[1] = true;
  int w, r, prm, prp;
  w = 0;
  r = b - 1;
  prm = 0;
  prp = 0;
  if (b % 2 == 0) {
    while (p[0] == true && r > (b - 2) / 2) {
      if (r != ((b - 2) / 2 + 1)) {
        if (prm == 0 && prp == 0) {
          if (a[w] == a[r]) {
            ans[w] = a[w];
            ans[r] = 0;
          } else {
            if (a[w] == a[r] + 1) {
              prm = 1;
              prp = 0;
              ans[w] = a[r];
              ans[r] = 0;
            } else {
              p[0] = 0;
            }
          }
        } else {
          if (prm == 1 && prp == 0) {
            if (a[w] == a[r] && a[w] < 9) {
              ans[w] = 9;
              ans[r] = a[w] + 1;
              prp = 1;
              prm = 0;
            } else {
              if (a[w] == 0 && a[r] == 9) {
                prp = 0;
                prm = 1;
                ans[w] = 9;
                ans[r] = 0;
              } else {
                if (a[w] == a[r] + 1) {
                  prp = 1;
                  prm = 1;
                  ans[w] = 9;
                  ans[r] = a[r] + 1;
                } else {
                  p[0] = false;
                }
              }
            }
          } else {
            if (prp == 1 && prm == 0) {
              if (a[r] == a[w] && a[r] > 0) {
                prp = 0;
                prm = 1;
                ans[w] = a[r] - 1;
                ans[r] = 0;
              } else {
                if (a[w] == 9 && a[r] == 0) {
                  prp = 1;
                  prm = 0;
                  ans[w] = 9;
                  ans[r] = 0;
                } else {
                  if (a[r] == a[w] + 1) {
                    prm = 0;
                    prp = 0;
                    ans[w] = a[w];
                    ans[r] = 0;
                  } else {
                    p[0] = false;
                  }
                }
              }
            } else {
              if (prp == 1 && prm == 1) {
                if (a[r] == 0 && a[w] == 9) {
                  prm = 0;
                  ans[w] = 9;
                  ans[r] = 0;
                } else {
                  if (a[r] == a[w] + 1) {
                    prm = 0;
                    ans[w] = 9;
                    ans[r] = a[w] + 1;
                  } else {
                    if (a[r] == a[w]) {
                      prm = 1;
                      ans[w] = 9;
                      ans[r] = a[w];
                    } else {
                      p[0] = false;
                    }
                  }
                }
              }
            }
          }
        }
      } else {
        if (prm == 0 && prp == 0) {
          if (a[r] == a[w]) {
            ans[w] = a[w];
            ans[r] = 0;
          } else {
            p[0] = false;
          }
        } else {
          if (prm == 0 && prp == 1) {
            if (a[r] == a[w] + 1) {
              ans[w] = a[w];
              ans[r] = 0;
            } else {
              p[0] = false;
            }
          } else {
            if (prm == 1 && prp == 0) {
              if (a[w] == a[r] + 1) {
                ans[w] = 9;
                ans[r] = a[r] + 1;
              } else {
                p[0] = false;
              }
            } else {
              if (prm == 1 && prp == 1) {
                if (a[w] == a[r]) {
                  ans[w] = 9;
                  ans[r] = a[r];
                } else {
                  p[0] = false;
                }
              }
            }
          }
        }
      }
      w = w + 1;
      r = r - 1;
    }
  } else {
    prm = 0;
    prp = 0;
    w = 0;
    r = b - 1;
    p[0] = true;
    while (p[0] == true && r > b / 2 - 1) {
      if (r != b / 2) {
        if (prm == 0 && prp == 0) {
          if (a[w] == a[r]) {
            ans[w] = a[w];
            ans[r] = 0;
          } else {
            if (a[w] == a[r] + 1) {
              prm = 1;
              prp = 0;
              ans[w] = a[r];
              ans[r] = 0;
            } else {
              p[0] = false;
            }
          }
        } else {
          if (prm == 1 && prp == 0) {
            if (a[w] == a[r] && a[w] < 9) {
              ans[w] = 9;
              ans[r] = a[w] + 1;
              prp = 1;
              prm = 0;
            } else {
              if (a[w] == 0 && a[r] == 9) {
                prp = 0;
                prm = 1;
                ans[w] = 9;
                ans[r] = 0;
              } else {
                if (a[w] == a[r] + 1) {
                  prp = 1;
                  prm = 1;
                  ans[w] = 9;
                  ans[r] = a[r] + 1;
                } else {
                  p[0] = false;
                }
              }
            }
          } else {
            if (prp == 1 && prm == 0) {
              if (a[r] == a[w] && a[r] > 0) {
                prp = 0;
                prm = 1;
                ans[w] = a[r] - 1;
                ans[r] = 0;
              } else {
                if (a[w] == 9 && a[r] == 0) {
                  prp = 1;
                  prm = 0;
                  ans[w] = 9;
                  ans[r] = 0;
                } else {
                  if (a[r] == a[w] + 1) {
                    prm = 0;
                    prp = 0;
                    ans[w] = a[w];
                    ans[r] = 0;
                  } else {
                    p[0] = false;
                  }
                }
              }
            } else {
              if (prp == 1 && prm == 1) {
                if (a[r] == 0 && a[w] == 9) {
                  prm = 0;
                  ans[w] = 9;
                  ans[r] = 0;
                } else {
                  if (a[r] == a[w] + 1) {
                    prm = 0;
                    ans[w] = 9;
                    ans[r] = a[w] + 1;
                  } else {
                    if (a[r] == a[w]) {
                      prm = 1;
                      ans[w] = 9;
                      ans[r] = a[w];
                    } else {
                      p[0] = false;
                    }
                  }
                }
              }
            }
          }
        }
      } else {
        if (prm == 0 && prp == 0) {
          if (a[r] % 2 == 0) {
            ans[r] = a[r] / 2;
          } else {
            p[0] = false;
          }
        } else {
          if (prm == 0 && prp == 1) {
            if (a[r] % 2 == 1) {
              ans[r] = a[r] / 2;
            } else {
              p[0] = false;
            }
          } else {
            if (prp == 0 && prm == 1) {
              if (a[r] % 2 == 0) {
                ans[r] = 5 + a[r] / 2;
              } else {
                p[0] = false;
              }
            } else {
              if (prp == 1 && prm == 1) {
                if (a[r] % 2 == 1) {
                  ans[r] = (9 + a[r]) / 2;
                } else {
                  p[0] = false;
                }
              }
            }
          }
        }
      }
      w = w + 1;
      r = r - 1;
    }
  }
  if (p[0] == false) {
    for (int i = 0; i < b; i++) {
      ans[i] = 0;
    }
    w = 1;
    r = b - 1;
    prm = 1;
    prp = 0;
    if (a[0] != 1) {
      p[1] = false;
    }
    if (r % 2 == 0) {
      while (p[1] == true && r > (b - 1) / 2) {
        if (r != ((b - 1) / 2 + 1)) {
          if (prm == 0 && prp == 0) {
            if (a[w] == a[r]) {
              ans[w] = a[w];
              ans[r] = 0;
            } else {
              if (a[w] == a[r] + 1) {
                prm = 1;
                prp = 0;
                ans[w] = a[r];
                ans[r] = 0;
              } else {
                p[1] = false;
              }
            }
          } else {
            if (prm == 1 && prp == 0) {
              if (a[w] == a[r] && a[w] < 9) {
                ans[w] = 9;
                ans[r] = a[w] + 1;
                prp = 1;
                prm = 0;
              } else {
                if (a[w] == 0 && a[r] == 9) {
                  prp = 0;
                  prm = 1;
                  ans[w] = 9;
                  ans[r] = 0;
                } else {
                  if (a[w] == a[r] + 1) {
                    prp = 1;
                    prm = 1;
                    ans[w] = 9;
                    ans[r] = a[r] + 1;
                  } else {
                    p[1] = false;
                  }
                }
              }
            } else {
              if (prp == 1 && prm == 0) {
                if (a[r] == a[w] && a[r] > 0) {
                  prp = 0;
                  prm = 1;
                  ans[w] = a[r] - 1;
                  ans[r] = 0;
                } else {
                  if (a[w] == 9 && a[r] == 0) {
                    prp = 1;
                    prm = 0;
                    ans[w] = 9;
                    ans[r] = 0;
                  } else {
                    if (a[r] == a[w] + 1) {
                      prm = 0;
                      prp = 0;
                      ans[w] = a[w];
                      ans[r] = 0;
                    } else {
                      p[1] = false;
                    }
                  }
                }
              } else {
                if (prp == 1 && prm == 1) {
                  if (a[r] == 0 && a[w] == 9) {
                    prm = 0;
                    ans[w] = 9;
                    ans[r] = 0;
                  } else {
                    if (a[r] == a[w] + 1) {
                      prm = 0;
                      ans[w] = 9;
                      ans[r] = a[w] + 1;
                    } else {
                      if (a[r] == a[w]) {
                        prm = 1;
                        ans[w] = 9;
                        ans[r] = a[w];
                      } else {
                        p[1] = false;
                      }
                    }
                  }
                }
              }
            }
          }
        } else {
          if (prm == 0 && prp == 0) {
            if (a[r] == a[w]) {
              ans[w] = a[w];
              ans[r] = 0;
            } else {
              p[1] = false;
            }
          } else {
            if (prm == 0 && prp == 1) {
              if (a[r] == a[w] + 1) {
                ans[w] = a[w];
                ans[r] = 0;
              } else {
                p[1] = false;
              }
            } else {
              if (prm == 1 && prp == 0) {
                if (a[w] == a[r] + 1) {
                  ans[w] = 9;
                  ans[r] = a[r] + 1;
                } else {
                  p[1] = false;
                }
              } else {
                if (prm == 1 && prp == 1) {
                  if (a[w] == a[r]) {
                    ans[w] = 9;
                    ans[r] = a[r];
                  } else {
                    p[1] = false;
                  }
                }
              }
            }
          }
        }
        w = w + 1;
        r = r - 1;
      }
    } else {
      while (p[1] == true && r > (b - 1) / 2) {
        if (r != (b - 1) / 2 + 1) {
          if (prm == 0 && prp == 0) {
            if (a[w] == a[r]) {
              ans[w] = a[w];
              ans[r] = 0;
            } else {
              if (a[w] == a[r] + 1) {
                prm = 1;
                prp = 0;
                ans[w] = a[r];
                ans[r] = 0;
              } else {
                p[1] = false;
              }
            }
          } else {
            if (prm == 1 && prp == 0) {
              if (a[w] == a[r] && a[w] < 9) {
                ans[w] = 9;
                ans[r] = a[w] + 1;
                prp = 1;
                prm = 0;
              } else {
                if (a[w] == 0 && a[r] == 9) {
                  prp = 0;
                  prm = 1;
                  ans[w] = 9;
                  ans[r] = 0;
                } else {
                  if (a[w] == a[r] + 1) {
                    prp = 1;
                    prm = 1;
                    ans[w] = 9;
                    ans[r] = a[r] + 1;
                  } else {
                    p[1] = false;
                  }
                }
              }
            } else {
              if (prp == 1 && prm == 0) {
                if (a[r] == a[w] && a[r] > 0) {
                  prp = 0;
                  prm = 1;
                  ans[w] = a[r] - 1;
                  ans[r] = 0;
                } else {
                  if (a[w] == 9 && a[r] == 0) {
                    prp = 1;
                    prm = 0;
                    ans[w] = 9;
                    ans[r] = 0;
                  } else {
                    if (a[r] == a[w] + 1) {
                      prm = 0;
                      prp = 0;
                      ans[w] = a[w];
                      ans[r] = 0;
                    } else {
                      p[1] = false;
                    }
                  }
                }
              } else {
                if (prp == 1 && prm == 1) {
                  if (a[r] == 0 && a[w] == 9) {
                    prm = 0;
                    ans[w] = 9;
                    ans[r] = 0;
                  } else {
                    if (a[r] == a[w] + 1) {
                      prm = 0;
                      ans[w] = 9;
                      ans[r] = a[w] + 1;
                    } else {
                      if (a[r] == a[w]) {
                        prm = 1;
                        ans[w] = 9;
                        ans[r] = a[w];
                      } else {
                        p[1] = false;
                      }
                    }
                  }
                }
              }
            }
          }
        } else {
          if (prm == 0 && prp == 0) {
            if (a[r] % 2 == 0) {
              ans[r] = a[r] / 2;
            } else {
              p[1] = false;
            }
          } else {
            if (prm == 0 && prp == 1) {
              if (a[r] % 2 == 1) {
                ans[r] = a[r] / 2;
              } else {
                p[1] = false;
              }
            } else {
              if (prp == 0 && prm == 1) {
                if (a[r] % 2 == 0) {
                  ans[r] = 5 + a[r] / 2;
                } else {
                  p[1] = false;
                }
              } else {
                if (prp == 1 && prm == 1) {
                  if (a[r] % 2 == 1) {
                    ans[r] = (9 + a[r]) / 2;
                  } else {
                    p[1] = false;
                  }
                }
              }
            }
          }
        }
        w = w + 1;
        r = r - 1;
      }
    }
    if (p[1] == true && b > 1) {
      if (ans[1] > 0) {
        for (int i = 1; i < b; i++) {
          cout << ans[i];
        }
      } else {
        cout << 0;
      }
    } else {
      cout << 0;
    }
  } else {
    if (ans[0] > 0) {
      for (int i = 0; i < b; i++) {
        cout << ans[i];
      }
    } else {
      cout << 0;
    }
  }
  return 0;
}