import java.io.PrintWriter; import java.util.ArrayDeque; import java.util.Scanner; class Main { public static void main(String[] args) { new Main().run(); } class Tree { int n=1; int n_; long[] sum; int[] sum_parity; ArrayDeque[] lazy; long erase=-1; public Tree(int n_) { while (n(); } void push(int k,int l,int r) { while (!lazy[k].isEmpty()) { long key=lazy[k].pollFirst(); if (key==erase) { sum[k]=sum_parity[k]; } else { sum[k]+=key*(r-l); if (key%2==1) { sum_parity[k]=r-l-sum_parity[k]; } } if (2*k+1