int sign(int a) { return (a < 0) ? -1 : 1; }
int avg(int x, int y) { return (sign(x) == sign(y)) ? x+(y-x)/2 : (x+y)/2; }