Hati Massage(G)
Time Limit:10S Memory Limit:65536K
Description
Hati is a professional massagist. One day, Hati receives massage requests from n customers. The ith customer (1<=i<=n) requests massage service during the period from time ai to time bi (inclusive), and is willing to pay Hati ci. As different customers' requested periods may conflict, Hati can only select to accept some requests.
What baffles Hati is that one in n customers is possible to break appointment. However, he doesn't know at first which customer will do so, until the customer's requested period begins. Hati wants to make a decision, such that his earning can be maximized in the worst case.
At first, Hati selects to accept some customers' requests. He makes a list of those accepted requests, and massage according to the list. Once Hati finds a customer breaks appointment, Hati can affirm no other customers will do so, and he can rearrange the following requests. If ith customer breaks appointment, Hati can rearrange and begin to accept other customers' requests on time ai.
You need to help Hati to make this initial customer list, and calculate his earning in the worst case under such a list.
Input
Input contains several cases.
The first line of each case is n (1<=n<=10000). The i-th line of the following n lines contains ai, bi and ci(1<=ai<=bi<=10^6, 1<=ci<=10^5).
The last line of input is a zero.
Input contains 20 cases at most.
Output
For each case, output Hati's earning in the worst case, as well as his initial customer list in the format:
m k1 k2 ... km
This indicates that Hati initially decides to accept m customers, whose serial numbers are ranked in time order.
Sample Input
4
1 3 200
4 5 100
4 5 50
2 6 400
4
1 3 200
3 5 100
4 5 50
6 7 100
0
Sample Output
Case #1:
250
2 1 2
Case #2:
200
2 1 2
Instruction of Sample Case #1
Hati initially selects Customer 1 and Customer 2. Under such selection, there are three possibilities:
(a) No customer breaks appointment. Hati earns 300.
(b) Customer 1 breaks appointment. Hati re-selects Customer 4 and earns 400.
(c) Customer 2 breaks appointment. Hati re-selects Customer 3 and earns 250.
So, his earning in the worst case is 250.

A difficult problem(H)
Time Limit:10S Memory Limit:32768K
Description
For a sequence {A1, A2, ..., An} whose elements range from 1 to n, and a 1-n permutation {B1,B2,??,Bn}, sequence {C1,C2,??,Cn} is calculated by the following formula:
Ci=BABi-1
Bi-1 indicates the position of number i in sequence B. For example, n=3, B is {3,1,2}, then B3-1 =1 and B1-1 =2.
Given sequence {Ci}, how many {Ai} can obtain {Ci} by selecting proper {Bi}?
For example, C={1,2,3,4,5}, if and only if A={1,2,3,4,5}, C can be obtained by any possible {Bi}. In another word, whatever Bi is, if A={1,2,3,4,5}, you will obtain C={1,2,3,4,5}.
Input
Input contains several cases.
For each case, the first line is n (1 <= n <= 50), followed by a line of C1, C2, ..., Cn.
The last line of input contains a zero.
Output
For each case, output how many {Ai} can obtain {Ci} by selecting proper {Bi}.
Sample Input
5
1 2 3 4 5
5
2 2 2 2 2
5
3 2 5 2 2
0
Sample Output
Case 1:
1
Case 2:
5
Case 3:
120