Xsquare loves to play with numbers a lot. Today, he has a multi set S containing of N integer elements. At first, he has listed all the subsets of his multiset S and later replaced all the subsets with the maximum element present in the respective subset.
For example:
Consider the following multi set consisting of 3 elements S={1,2,3}
List of all subsets:
{}
{1}
{2}
{3}
{1,2}
{2,3}
{1,3}
{1,2,3}
Final List:
{0}
{1}
{2}
{3}
{2}
{3}
{3}
{3}
Now, Xsquare wonders that given an integer k how many elements in the final list are greater than (>) , less than (<) or equals to (==) k
Input:
3 5
1 2 3
< 1
> 1
= 3
= 2
> 3
Output:
1
6
4
2
0
Python Implementation:
For example:
Consider the following multi set consisting of 3 elements S={1,2,3}
List of all subsets:
{}
{1}
{2}
{3}
{1,2}
{2,3}
{1,3}
{1,2,3}
Final List:
{0}
{1}
{2}
{3}
{2}
{3}
{3}
{3}
Now, Xsquare wonders that given an integer k how many elements in the final list are greater than (>) , less than (<) or equals to (==) k
Input:
3 5
1 2 3
< 1
> 1
= 3
= 2
> 3
Output:
1
6
4
2
0
Python Implementation: