15896번 - &+ +&

문제

길이 N의 자연수 수열 2개 A₁, A₂, ..., A_N과 B₁, B₂, ..., B_N이 주어진다. 다음 2가지 값을 구하여라.

• 모든 (A_i & B_j)의 합을 1999로 나눈 나머지
• 모든 (A_i + B_j)의 bitwise and 연산 값

여기서 &는 bitwise and 연산을 의미한다. bitwise and 연산의 정의는 하단의 참고 사항에 있다.

입력

첫 번째 줄에 수열의 길이를 나타내는 자연수 N(1 ≤ N ≤ 10⁶)이 주어진다. 두 번째 줄에 수열 A를 나타내는 수 N개가 공백으로 구분되어 주어지고, 세 번째 줄에 수열 B를 나타내는 수 N개가 공백으로 구분되어 주어진다. A, B 수열의 모든 수는 1 이상 2²⁸ 이하의 자연수이다.

출력

첫 번째 줄에 위에서 언급한 2가지 값을 공백으로 구분하여 순서대로 출력한다.

제한

힌트

bitwise and 연산은 두 개의 이진수 값에 대해 자리 단위로 적용되는 연산이다. 먼저 피연산자로 주어진 두 값을 2진수로 표현한다. 그 뒤에 두 값의 각 자릿수를 비교해, 두 값 모두에 1이 있을 때만 1을, 나머지 경우에는 0을 계산한다.

예를 들어 13 & 7의 값은 5이다. 13은 2진수로 표현하면 1101₍₂₎ 이고 7은 2진수로 표현하면 111₍₂₎ 이다. 이후의 계산과정은 아래와 같다.