F. Stage 4
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a value $$$x$$$, a permutation $$$p$$$ of length $$$n$$$, and an array $$$q$$$ of length $$$n$$$. For every $$$p_i$$$, you must choose to either set $$$x := x + p_i$$$ or set $$$x := x \oplus 2^{d(p_i)}$$$, where $$$\oplus$$$ denotes the bitwise XOR operation and $$$d(a)$$$ denotes the sum of the digits of $$$a$$$ in its decimal representation. For each $$$k$$$ ($$$1 \le k \le n$$$), find the number of possible values of $$$x$$$ that satisfy $$$x \leq q_k$$$ after processing the elements $$$p_1, p_2, \ldots, p_k$$$ in order from $$$1$$$ to $$$k$$$.

Input

The first line of input contains two integers $$$n$$$ and $$$x$$$ $$$(1 \leq n \leq 500, 1 \leq x \leq 5 \cdot 10^6)$$$ — the length of the permutation $$$p$$$ and the starting value of $$$x$$$.

The second line of input contains $$$n$$$ integers $$$p_1, p_2, \ldots, p_n$$$ $$$(1 \leq p_i \leq n)$$$. It is guaranteed that $$$p$$$ is a permutation.

The third line contains $$$n$$$ integers $$$q_1, q_2, \ldots, q_n$$$ $$$(1 \leq q_i \leq 5 \cdot 10^6)$$$.

—

Tests in subtasks are numbered from $$$1-20$$$ with samples skipped. Each test is worth $$$\frac{100}{20} = 5$$$ points.

Test $$$1$$$ satisfies $$$n \leq 20$$$, $$$x \leq 100$$$.

Tests $$$2-4$$$ will satisfy $$$n \leq 200$$$, $$$x \leq 10^5$$$.

Tests $$$5-12$$$ will satisfy $$$n \leq 400$$$.

The remaining tests do not satisfy any additional constraints.

Output

Print $$$n$$$ lines, the $$$i$$$-th line containing a single integer denoting the number of possible values of $$$x$$$ that satisfy $$$x \leq q_i$$$ after processing the prefix $$$p_1, p_2, \ldots, p_i$$$.

Example
Input
3 2
1 3 2
2 3 8
Output
1
1
4
Note

In the sample test, you're given the permutation $$$p=[1, 3, 2]$$$ and an initial $$$x$$$ value of 2.

For the prefix $$$[p_1]$$$, the two possible values of $$$x$$$ you can achieve are $$$2 + 1 = 3$$$ and $$$2 \oplus (2^1) = 0$$$. Since only $$$x = 0$$$ satisfies $$$x \leq q_1 = 2$$$, the answer for this prefix is $$$1$$$.

For the prefix $$$[p_1, p_2]$$$, the possible values of $$$x$$$ are $$$3, 6, 8, 11$$$. Since only $$$x=3$$$ satisfies $$$x \leq q_2=3$$$, the answer is $$$1$$$.

For the prefix $$$[p_1, p_2, p_3]$$$, the possible values of $$$x$$$ are $$$2, 5, 7, 8, 10, 12, 13, 15$$$. Four of these satisfy $$$x \leq q_3=8$$$, so the answer is $$$4$$$.

—

Problem Idea: Yam, willy108

Problem Preparation: Yam

Occurrences: Advanced F