After learning the basics of matrices, Derar wants to learn the newest matrix algorithm "Matrix Bel Lotus."
Ahmad, its author, gave Derar $$$n$$$ videos. Video $$$i$$$ is $$$d_i$$$ minutes long.
Derar has $$$T$$$ minutes before the contest, and he has to watch all the videos. He can't skip a video, but he can watch video $$$i$$$ with any of the following speeds:
It is guaranteed that $$$d_i$$$ is a multiple of $$$6$$$. So it can be proven that all the values in the problem are integers. And it is guaranteed that Derar can watch all the videos if he plays them at speed X$$$2$$$.
You have to help Derar choose the speed of each video so he can watch all the videos in at most $$$T$$$ minutes and maximize the total sum of skill points.
The first line contains a single integer $$$tc \: (1 \leq tc \leq 100)$$$ — the number of testcases.
The first line of each testcase consists of two integers $$$n , T \: (1 \leq n \leq 2 \cdot 10^5) (1 \leq T \leq 10^{10})$$$ — the number of videos and the number of minutes Derar has before the contest.
The second line of each testcase consists of $$$n$$$ integers $$$d_i \: (1 \leq d_i \leq 10^{10}) $$$ — the duration of each video. It is guaranteed that $$$d_i$$$ is a multiple of $$$6$$$.
It is guaranteed that the sum of $$$n$$$ over all testcases doesn't exceed $$$2 \cdot 10^5$$$ , and Derar can watch all the videos if he plays them at speed X$$$2$$$.
The output of each testcase consists of two lines:
On the first line, print the maximum sum of skill points Derar can achieve.
On the second line, print $$$n$$$ values, the speed he will watch each video with. The values should be $$$1 , 1.5$$$ or $$$2$$$.
If there are multiple solutions, print any.
23 186 6 63 8436 24 60
300 1 1 1 225 1.5 1 2
