VO 19 Bài 4 - Cá cược uống bia


Submit solution

Points: 0.50 (partial)
Time limit: 2.0s
Memory limit: 512M

Problem type

Sau khi xuất sắc cùng đội VECTOR dành vị trí á quân tại Kì thi Lập trình sinh viên quốc tế The ~2018~ ICPC Asia Yangon Regional Contest tại Myanmar, Thắng dễ thương và Đức gáy to lấy giải thưởng khao cả đoàn đi chơi tẹt ga. Tuy nhiên, họ cũng không quên sát phạt nhau trong quán bar.

Số là, mặc dù giải được rất nhiều bài, nhưng số lần nộp của họ cũng hoành tráng không kém. Có những người không tin tưởng vào code của đồng đội lắm, có những người khác thì lại quá tự tin khi nộp bài. Vì vậy, họ quyết định cá cược kết quả nộp bài bằng những chầu bia.

Những màn cá cược trong phòng thi khép lại, theo kết quả tạm thời, Thắng dễ thương phải uống ~A~ cốc bia còn Đức gáy to phải uống ~B~ cốc bia. Tuy nhiên, khi ra đến quán bar, họ nhận ra cốc bia tại đây to quá; và sau khi uống lượng bia kia vào, họ không cho chó ăn chè thì cũng phải đi gặp em Huệ gấp. Bởi vậy, họ muốn giảm số lượng bia mình cần uống, đồng thời tăng số lượng bia đối phương phải uống. GSPVH được giao nhiệm vụ giải quyết tranh chấp này.

GSPVH cho hai bạn chơi boardgame Bears vs Babies. Trước mỗi ván, GSPVH chọn ra một số nguyên dương ~P~ không quá ~10^{7}~. Dựa trên kết quả của trò chơi (thắng, hoà hoặc thua); số cốc bia mỗi người phải uống thay đổi như sau:

  • Nếu Đức gáy to thắng, Thắng dễ thương phải uống gấp ~P~ lần số cốc bia trước đó, còn Đức gáy to được uống số cốc bia giảm đi ~P^{2}~ lần.
  • Nếu Thắng dễ thương thắng, số cốc bia của Thắng dễ thương giảm đi ~P^{2}~ lần.
  • Nếu hai người hoà nhau, Đức gáy to thể hiện tinh thần nhường nhịn đàn em bằng việc tự gấp ~P~ lần số cốc bia mình uống.

Do quá hiểu chiến thuật chơi của hai bên, GSPVH hoàn toàn có thể dàn xếp tỷ số (quyết định ai thắng hoặc cho hai người hoà nhau) bằng cách tráo bài theo thứ tự thích hợp. Nhưng để tránh các rắc rối không đáng có, GSPVH muốn dàn xếp sao cho sau mỗi ván chơi, số cốc bia mỗi người phải uống là số nguyên dương; nói cách khác, mọi phép chia nếu cần thiết đều cho kết quả chia hết. Vì thời gian có hạn, GSPVH không thể tổ chức quá ~10^6 = 1000000~ ván chơi. GSPVH không muốn mang đội quân say xỉn từ Myanmar trở về, nên muốn sắp xếp kết quả các ván chơi, cũng như chọn các hệ số; sao cho tổng số cốc bia hai người phải uống là nhỏ nhất. Các bạn hãy giúp GSPVH nhé.

Input

Trong bài này, thay vì cho trước hai số ~A~ và ~B~; bạn cần đọc vào hai dãy số ~P_1, P_2, \dots, P_m~ và ~Q_1, Q_2, \dots, Q_n~ rồi tính giá trị của ~A~ và ~B~ theo công thức sau: $$ A = \prod_{i=1}^{m}P_i = P_1 \times P_2 \times \dots \times P_n$$ $$ B = \prod_{j=1}^{n}Q_i = Q_1 \times Q_2 \times \dots \times Q_n$$

  • Dòng đầu tiên ghi một số nguyên ~m~ ~(1 \leq m \leq 300)~.
  • Dòng thứ hai ghi ~m~ số nguyên ~P_1~ ~P_2~ ~\dots~ ~P_m~ ~(1 \leq P_i \leq 10^{7})~.
  • Dòng thứ bai ghi một số nguyên ~n~ ~(1 \leq n \leq 300)~.
  • Dòng thứ tư ghi ~n~ số nguyên ~Q_1~ ~Q_2~ ~\dots~ ~Q_n~ ~(1 \leq Q_j \leq 10^{7})~.

    Output

  • Dòng đầu tiên ghi một số nguyên ~k~ ~(0 \leq k \leq 10^6)~ – số game GSPVH cần tổ chức.

  • ~k~ dòng tiếp theo, dòng thứ ~i~ mô tả ván thứ ~i~ bởi số nguyên ~P~ ~(1 \leq P \leq 10^7)~ – hệ số của ván đấu, và một trong ba chữ cái ~W~, ~D~ và ~L~ – kết quả của ván đấu đó ~(W =~ Đức gáy to thắng, ~D =~ hai bạn hoà nhau, ~L =~ Thắng dễ thương thắng).

Nếu có nhiều đáp án tối ưu, bạn có thể in ra phương án bất kỳ

Giới hạn

  • Subtask ~1~ ~(21/70~ điểm): ~A~, ~B \leq 25~
  • Subtask ~2~ ~(21/70~ điểm): Với mọi số nguyên ~x > 1~, cả ~A~ và ~B~ đều không chia hết cho ~x~
  • ~2~.
  • Subtask ~3~ ~(28/70~ điểm): Không có ràng buộc gì thêm.

Sample Input

2
6 7
3
7 3 2

Sample Output

5
42 D
6 W
7 W
14 L
3 L

Giải thích

Ban đầu số cốc bia hai người cần uống là ~(A, B) = (42, 42)~. GSPVH cho chơi ~5~ ván:

  • Ván ~1~: ~P = 42~, hai người hoà nhau. Số cốc bia là ~(A, B) = (42, 42 \times 42) = (42, 1764)~.
  • Ván ~2~: ~P = 6~, Đức gáy to thắng. Số cốc bia là ~(A, B) = (42 \times 6, \frac{1764}{6^{2}}) = (252, 49)~.
  • Ván ~3~: ~P = 7~, Đức gáy to thắng. Số cốc bia là ~(A, B) = (252 \times 7, \frac{49}{7^{2}}) = (1764, 1)~.
  • Ván ~4~: ~P = 14~, Thắng dễ thương thắng. Số cốc bia là ~(A, B) = (\frac{1764}{14^{2}}, 1) = (9, 1)~.
  • Ván ~5~: ~P = 3~, Thắng dễ thương thắng. Số cốc bia là ~(A, B) = (\frac{9}{3^{2}}, 1) = (1, 1)~.

Sau ~5~ ván, tổng số cốc bia hai người cần uống là ~A + B = 1 + 1 = 2~.


Comments

There are no comments at the moment.