This is the easy version of the problem. The only difference between easy and hard versions is the constraint of $m$. You can make hacks only if both versions are solved.

Chiori loves dolls and now she is going to decorate her bedroom![Image] 

As a doll collector, Chiori has got $n$ dolls. The $i$-th doll has a non-negative integer value $a_i$ ($a_i < 2^m$, $m$ is given). Chiori wants to pick some (maybe zero) dolls for the decoration, so there are $2^n$ different picking ways.

Let $x$ be the bitwise-xor-sum of values of dolls Chiori picks (in case Chiori picks no dolls $x = 0$). The value of this picking way is equal to the number of $1$-bits in the binary representation of $x$. More formally, it is also equal to the number of indices $0 \leq i < m$, such that $\left\lfloor \frac{x}{2^i} \right\rfloor$ is odd.

Tell her the number of picking ways with value $i$ for each integer $i$ from $0$ to $m$. Due to the answers can be very huge, print them by modulo $998\,244\,353$.


-----Input-----

The first line contains two integers $n$ and $m$ ($1 \le n \le 2 \cdot 10^5$, $0 \le m \le 35$)  — the number of dolls and the maximum value of the picking way.

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($0 \le a_i < 2^m$)  — the values of dolls.


-----Output-----

Print $m+1$ integers $p_0, p_1, \ldots, p_m$  — $p_i$ is equal to the number of picking ways with value $i$ by modulo $998\,244\,353$.


-----Examples-----
Input
4 4
3 5 8 14

Output
2 2 6 6 0 
Input
6 7
11 45 14 9 19 81

Output
1 2 11 20 15 10 5 0

Difficulty: HARD

Starter code:

Solutions:
MOD = 998244353
BOUND = 19
(n, m) = map(int, input().split())
l = list(map(int, input().split()))
basis = []
for p in range(m - 1, -1, -1):
	p2 = pow(2, p)
	nex = -1
	for i in range(n):
		if l[i] >= p2:
			nex = l[i]
			break
	if nex != -1:
		basis.append(nex)
		for i in range(n):
			if l[i] >= p2:
				l[i] ^= nex
extra = n - len(basis)

def add(a, b):
	out = [0] * max(len(a), len(b))
	for i in range(len(a)):
		out[i] = a[i]
	for i in range(len(b)):
		out[i] += b[i]
		out[i] %= MOD
	return out

def addSh(a, b):
	out = [0] * max(len(a) + 1, len(b))
	for i in range(len(a)):
		out[i + 1] = a[i]
	for i in range(len(b)):
		out[i] += b[i]
		out[i] %= MOD
	return out
i = 0
curr = dict()
curr[0] = [1]
for p in range(m - 1, -1, -1):
	p2 = pow(2, p)
	if i < len(basis) and basis[i] >= p2:
		currN = dict(curr)
		for v in curr:
			if v ^ basis[i] not in currN:
				currN[v ^ basis[i]] = [0]
			currN[v ^ basis[i]] = add(curr[v], currN[v ^ basis[i]])
		curr = currN
		i += 1
	currN = dict(curr)
	for v in curr:
		if v >= p2:
			if v ^ p2 not in currN:
				currN[v ^ p2] = [0]
			currN[v ^ p2] = addSh(curr[v], currN[v ^ p2])
			del currN[v]
	curr = currN
out = curr[0]
while len(out) < m + 1:
	out.append(0)
for i in range(m + 1):
	out[i] *= pow(2, extra, MOD)
	out[i] %= MOD
print(' '.join(map(str, out)))


import sys
MOD = 998244353
BOUND = 21
(n, m) = map(int, input().split())
l = list(map(int, input().split()))
basis = []
for p in range(m - 1, -1, -1):
	p2 = pow(2, p)
	nex = -1
	for i in range(n):
		if l[i] >= p2:
			nex = l[i]
			break
	if nex != -1:
		basis.append(nex)
		for i in range(n):
			if l[i] >= p2:
				l[i] ^= nex
extra = n - len(basis)

def add(a, b):
	out = [0] * max(len(a), len(b))
	for i in range(len(a)):
		out[i] = a[i]
	for i in range(len(b)):
		out[i] += b[i]
		out[i] %= MOD
	return out

def addSh(a, b):
	out = [0] * max(len(a) + 1, len(b))
	for i in range(len(a)):
		out[i + 1] = a[i]
	for i in range(len(b)):
		out[i] += b[i]
		out[i] %= MOD
	return out
i = 0
curr = dict()
curr[0] = [1]
for p in range(m - 1, -1, -1):
	if p == m - 1 and p < BOUND:
		curr = [curr[i] if i in curr else [] for i in range(2 ** 20)]
	if p >= BOUND:
		p2 = pow(2, p)
		if i < len(basis) and basis[i] >= p2:
			currN = dict(curr)
			for v in curr:
				if v ^ basis[i] not in currN:
					currN[v ^ basis[i]] = [0]
				currN[v ^ basis[i]] = add(curr[v], currN[v ^ basis[i]])
			curr = currN
			i += 1
		lis = list(curr.keys())
		for v in lis:
			if v >= p2:
				if v ^ p2 not in currN:
					curr[v ^ p2] = [0]
				curr[v ^ p2] = addSh(curr[v], curr[v ^ p2])
				del curr[v]
	else:
		p2 = pow(2, p)
		if i < len(basis) and basis[i] >= p2:
			for v in range(p2):
				curr[v ^ basis[i]] = add(curr[v], curr[v ^ basis[i]])
				curr[v] = curr[v ^ basis[i]]
			i += 1
		for v in range(p2):
			curr[v] = addSh(curr[v ^ p2], curr[v])
	if p == BOUND:
		curr = [curr[i] if i in curr else [] for i in range(2 ** BOUND)]
out = curr[0]
while len(out) < m + 1:
	out.append(0)
for i in range(m + 1):
	out[i] *= pow(2, extra, MOD)
	out[i] %= MOD
for v in out:
	sys.stdout.write(str(v) + ' ')