|시간 제한||메모리 제한||제출||정답||맞은 사람||정답 비율|
|5 초||512 MB||4||2||2||50.000%|
You recently did a fabulous prank on your superior officer. And it worked extremely well – you were promptly demoted, relieved of your post and assigned to command the elite platoon of carefully hand-picked soldiers, the famous Halfwitters. It is said that no Halfwitter has ever been suborned by the enemy or disgraced themselves in battle – they simply do not understand the concepts of retreat or betrayal. And no Halfwitter has ever served in a place where outside temperature could fall below their IQ.
The platoon, consisting of n soldiers, is standing in a row before you. You would like the men to stand from the tallest one (number 1) to the smallest (number n). This, however, has yet to be explained to the platoon. Right now, they are standing in their favourite order of whoever-was-the-first-to-finish-their-dessert. You may take the following three actions:
Assuming the best strategy possible, what is the expected time to achieve the desired order of (1, 2, . . . , n)? You will drill the platoon for d days, every day starting with possibly different order, because of various available desserts. Compute the answer for each day.
The first line of input contains the number of test cases z. The descriptions of the test cases follow.
Every test case starts with a line consisting of five integers n, a, b, c, d (2 ≤ n ≤ 16, 1 ≤ a, b, c ≤ 1000, 1 ≤ d ≤ 10 000) – the number of soldiers, the costs of each action, and the number of days. Each of the next d lines contains a permutation of the sequence (1, 2, . . . , n) – the initial order of soldiers on consecutive days. The total number of days in all test cases does not exceed 100 000.
For each test case output d lines – for every day, output the expected time needed to arrange the soldiers. As this is a rational number, express it as an irreducible fraction of the form p/q.
1 6 1 1 1 3 1 2 3 4 5 6 5 4 3 2 1 6 6 4 2 1 3 5
0/1 6/1 2771/428