24397번 - 말해 xor NO!

중앙대학교의 자랑스러운 청룡 푸앙이는 요즘 즐겨 듣는 노래가 있다. 〈Show me the 중앙〉에 나온 '말해 xor NO!' 라는 노래이다. 노래에 심취한 푸앙이는 노래의 제목대로 '말해 xor NO!'를 계산하기 위해 N장의 '말해' 카드와 M장의 'NO!' 카드를 만들었다.

정수 n이 쓰여 있는 '말해' 카드와 m이 쓰여 있는 'NO!' 카드를 하나씩 뽑았을 때, 두 카드에 대한 '말해 xor NO!' 연산의 값은 n xor m으로 정의한다.

올해 K살이 되는 푸앙이는 '말해 xor NO!' 연산을 한 결과가 자신의 나이보다 작은 경우의 수가 얼마나 있는지 궁금해졌다. 푸앙이를 위해 경우의 수를 계산하는 프로그램을 만들어주자!

첫째 줄에 '말해' 카드의 개수 N(1 ≤ N ≤ 100,000)과 'NO!' 카드의 개수 M(1 ≤ M ≤ 100,000), 푸앙이의 나이 K(​1 ≤ K ≤ 10⁹)가 주어진다. 다음 줄에는 '말해' 카드에 적힌 수 a₁, a₂, ..., a_N이 공백으로 구분되어 주어진다. 마지막 줄에는 'NO!' 카드에 적힌 수 b₁, b₂, ..., b_M이 공백으로 구분되어 주어진다. (1 ≤ a_i, b_i ≤ 10⁹)

첫째 줄에 bitwise xor 연산을 한 값이 K보다 작은 카드 쌍의 개수를 출력한다.

xor 연산의 정의는 여기에서 확인할 수 있다.