모자이크

살마는 벽에 붙일 점토 모자이크를 칠할 계획이다. 모자이크는 처음에는 색이 칠해지지 않은 $1 \times 1$ 정사각형 타일 $N$개로 이루어진 $N \times N$ 격자이다. 행은 위에서 아래로 $0$번부터 $N - 1$번까지, 열은 왼쪽에서 오른쪽으로 $0$번부터 $N - 1$번까지 번호가 매겨진다. 행 $i$, 열 $j$에 있는 타일은 $(i, j)$로 나타낸다($0 \le i < N$, $0 \le j < N$). 각 타일은 흰색($0$) 또는 검은색($1$) 중 하나로 칠해야 한다.

모자이크를 칠하기 위해 살마는 먼저 길이가 $N$인 배열 $X$와 $Y$를 고른다. 두 배열의 원소는 모두 $0$ 또는 $1$이며, $X[0] = Y[0]$을 만족해야 한다. 살마는 최상단 행(행 $0$)의 타일 $(0, j)$를 $X[j]$의 색으로 칠한다($0 \le j < N$). 또 최좌측 열(열 $0$)의 타일 $(i, 0)$은 $Y[i]$의 색으로 칠한다($0 \le i < N$).

그다음 모든 타일이 칠해질 때까지 다음 과정을 반복한다.

• 위쪽 이웃 타일 $(i-1, j)$와 왼쪽 이웃 타일 $(i, j-1)$이 모두 이미 칠해져 있는, 칠해지지 않은 타일 $(i, j)$를 임의로 하나 찾는다.
• 두 이웃 타일이 모두 흰색이면 타일 $(i, j)$를 검은색으로 칠하고, 그렇지 않으면 흰색으로 칠한다.

타일의 최종 색은 살마가 칠하는 순서와 관계없다는 것이 증명되어 있다.

야스민은 모자이크의 색에 큰 관심이 있다. 그녀는 살마에게 $Q$개의 질문을 하며, 질문 번호는 $0$부터 $Q - 1$까지이다. 질문 $k$($0 \le k < Q$)에서 야스민은 모자이크의 부분 직사각형을 다음 값으로 지정한다.

• 최상단 행 $T[k]$와 최하단 행 $B[k]$($0 \le T[k] \le B[k] < N$)
• 최좌측 열 $L[k]$와 최우측 열 $R[k]$($0 \le L[k] \le R[k] < N$)

답은 이 부분 직사각형에 있는 검은색 타일의 개수이다. 구체적으로, $T[k] \le i \le B[k]$, $L[k] \le j \le R[k]$를 만족하고 타일 $(i, j)$가 검은색인 타일 $(i, j)$의 개수를 구해야 한다.

야스민의 질문에 답하는 프로그램을 작성하라.

• $1 \le N \le 200\,000$
• $1 \le Q \le 200\,000$
• $0 \le i < N$을 만족하는 모든 $i$에 대해 $X[i] \in \{0, 1\}$이고 $Y[i] \in \{0, 1\}$이다.
• $X[0] = Y[0]$
• $0 \le k < Q$를 만족하는 모든 $k$에 대해 $0 \le T[k] \le B[k] < N$이고 $0 \le L[k] \le R[k] < N$이다.