Mừng giao diện mới

Points: 300.00 (partial)

Time limit: 1.0s

Memory limit: 256M

Input: stdin

Output: stdout

Author:

LeKienThanh

Problem type

Allowed languages

C, C++, GAS64, ~~Java~~, Pascal, Perl, PHP, Python, Sed, TCL, Text

Nhân dịp web trường đổi giao diện mới, LeKienThanh đã nghĩ ra một bài toán thú vị sau:
Cho hai số nguyên dương ~n~ và ~m~, cùng với hai dãy ~A~ và ~B~ có độ dài ~2^n~ và được đánh số từ 0 đến ~2^n-1~. Ta có dãy ~C~ cũng có độ dài ~2^n~ và được đánh số từ ~0~ đến ~2^n-1~, được tính toán theo công thức sau:

~ C[k] = \displaystyle\sum_{i \vee j = k} A[i] * B[j] ~
Chú thích: ~\vee~ là phép toán OR.

Đáng tiếc thay, vì LeKienThanh rất gà, chỉ đạt nhì VOI chứ không vào nổi TST, nên anh ấy không biết cách giải bài toán này khi ~n~ trở nên quá lớn. Các bạn lập trình viên hãy chứng minh bạn pro hơn LeKienThanh và xứng đáng vào vòng 2 nhé.

Input:

Dòng thứ nhất chứa hai số nguyên dương ~n~ và ~m~ (~100 \leq m \leq 999~)

Dòng thứ hai chứa ~2^n~ số nguyên trong khoảng ~[0, m)~ là các phần tử của dãy ~A~.

Dòng thứ ba chứa ~2^n~ số nguyên trong khoảng ~[0, m)~ là các phần tử của dãy ~B~.

Output:

In ra ~2^n~ phần tử của dãy ~C~ chia dư cho ~m~.

Sample Input:

2 999
1 2 3 4
5 6 7 8

Sample Output:

5 28 43 184

Subtask 1: (50% số điểm): ~n \leq 10~.
Subtask 2: (50% số điểm): ~n \leq 20~.

Comments

Please read the guidelines before commenting.

1

UltimateWiener commented on Aug. 27, 2023, 1:47 p.m.

easy problem https://codeforces.com/blog/entry/115438