정원 (Hard)

이 문제는 "정원 (Easy)" 문제와 $N$, $M$의 제한을 제외하고 같은 문제이다.

정원사 지은이에게는 세로 $N$, 가로 $M$ 크기의 직사각형 모양 정원이 있다. 정원의 가장자리에 꽃들이 피어 있는 것을 본 지은이는 정원에도 꽃을 심기로 결정하였다. 지은이는 정원에 어떻게 꽃을 심을지에 대한 규칙을 정했는데, 그 규칙은 아래와 같다.

• 정원을 $N$행 $M$열의 격자판으로 생각하여, 격자 한 칸에 하나씩 꽃을 심는다. 정원의 왼쪽, 위쪽 가장자리에도 정원의 격자와 동일한 간격으로 각각 $N$개, $M$개의 꽃이 피어 있다.
• 꽃은 행 번호가 작은 칸부터, 행 번호가 같다면 열 번호가 작은 칸부터 심는다.
• 정원의 각 칸에 꽃을 심을 때는 왼쪽과 위쪽 칸에 이미 심어져 있는 꽃의 색을 보고, 두 꽃의 색이 같다면 노란색 꽃, 다르다면 빨간색 꽃을 심는다. 1행 또는 1열에 꽃을 심을 때는 각각 위쪽 가장자리, 왼쪽 가장자리에 피어 있는 꽃의 색을 보고 판단한다.

이러한 규칙에 따라 꽃을 심었을 때, 지은이는 $N$행 $M$열에 해당하는 칸에 어떤 색의 꽃을 심게 될지 궁금해졌다. 이를 알아내는 프로그램을 작성해 보자.

첫번째 줄에는 정원의 세로 길이 $N$ 과 가로 길이 $M$ 이 주어진다. ($1 \le N, M \le 100,000$)

두번째 줄에는 정원의 왼쪽 가장자리에 피어 있는 꽃 $N$ 개의 정보가 공백을 사이에 두고 주어진다. $i$번째 수는 정원의 $i$행 왼쪽에 피어 있는 꽃의 정보이며, $0$ 이라면 노란색 꽃, $1$ 이라면 빨간색 꽃을 의미한다. ($1 \le i \le N$)

세번째 줄에는 정원의 위쪽 가장자리에 피어 있는 꽃 $M$ 개의 정보가 공백을 사이에 두고 주어진다. $j$번째 수는 정원의 $j$열 위쪽에 피어 있는 꽃의 정보이며, $0$ 이라면 노란색 꽃, $1$ 이라면 빨간색 꽃을 의미한다. ($1 \le j \le M$)

$N$행 $M$열에 해당하는 칸에 심어야 할 꽃이 노란색일 경우 $0$, 빨간색일 경우 $1$을 출력한다.