K. Strange Array
time limit per test
5 s
memory limit per test
512 megabytes
input
standard input
output
standard output

You are given three integers $$$n$$$, $$$k$$$ and $$$m$$$. Additionally, you have $$$m$$$ integer triples ($$$l_i, r_i, x_i$$$).

Let's define the value of an integer array $$$a$$$ as follows:

  • let $$$A$$$ be the bitwise OR of all elements of the array;
  • let $$$y_i$$$ be the bitwise XOR of $$$a[l_i], a[l_i+1], \dots, a[r_i]$$$;
  • let $$$z_i$$$ be the bitwise AND of $$$y_i$$$ and $$$x_i$$$;
  • the value of the array is $$$k \cdot A - \sum \limits_{i=1}^{m} z_i$$$.
Your task is to find an array $$$a$$$ consisting of $$$n$$$ integers from $$$0$$$ to $$$2^{30} - 1$$$ with the maximum value.
Input

The first line contains three integers $$$n, k$$$ and $$$m$$$ ($$$1 \le n, k \le 100$$$; $$$0 \le m \le 5000$$$).

Then $$$m$$$ lines follow. The $$$i$$$-th of them contains three integers $$$l_i, r_i$$$ and $$$x_i$$$ ($$$1 \le l_i \le r_i \le n$$$; $$$0 \le x \lt 2^{30}$$$).

Output

Print $$$n$$$ integers — the array consisting of $$$n$$$ integers from $$$0$$$ to $$$2^{30} - 1$$$ with the maximum value.

Examples
Input
3 2 4
3 3 1
1 2 3
1 1 1
1 3 3
Output
3 3 1073741820
Input
2 2 0
Output
0 1073741823