Welcome to ZOJ
Information
Select Problem
Runs
Ranklist
ZOJ Problem Set - 3851
Bizarre Routine

Time Limit: 2 Seconds      Memory Limit: 65536 KB      Special Judge

We've got a bizarre routine here:

bool less_than(x, y) {
	T++;
	return x < y;
}
void work(array[], l, r) {
	if (l >= r) return;
	swap(array[(l * A + r * B) / (A + B)], array[r]);
	int index = l;
	for (i = l; i < r; i++)
		if (less_than(array[i], array[r]))
			swap(array[index++], array[i]);
	swap(array[r], array[index]);
	work(array, l, index - 1);
	work(array, index + 1, r);
}
void main() {
	T = 0;
	Input(n, expect, A, B, array[]);
	work(array, 0, n - 1);
	if (T == expect)
		Output("YES");
	else
		Output("NO");
}

Now the question is: For given n, expect, A and B, how to arrange the input array to make the routine output "YES"?

To simplify the problem, we assume that the input array must be a permutation of 1 to n, and the division in the routine is integer division.

Input

There will be no more than 100 test cases, each case contains 4 integers n (1 ≤ n ≤ 10000), expect (1 ≤ expect ≤ 100000000), A (1 ≤ A ≤ 10) and B (1 ≤ B ≤ 10) in one line.

Output

If there exists an arrangement to make the routine output "YES", please print these corresponding n integers in one line, and seperate them by single spaces. Please be aware that these n integers must be a permutation of 1 to n and the answer might not be unique.

If there isn't any arrangement to make it output "YES", please print "NOWAY" in a line.

Sample Input

6 10 2 1
12 15 1 1

Sample Output

4 5 1 2 3 6
NOWAY

Source: 2013 ACM/ICPC Asia Regional Changsha Online contest
Submit    Status