One wall of the house he lives in is a rectangle built from square bricks of size 1×1, stacked in H rows and W columns.
The house has no window and feels stuffy, so he wants to remove some bricks and open one. Because the hole becomes a window, the removed bricks must form a single solid rectangle.
He decides to think about mounting the window later and first to fix the spot the window will occupy, then remove every brick in that spot. He likes randomness, so he picks one of the 2H(H+1)×2W(W+1) possible window positions uniformly at random and removes every brick in it. Removing one brick costs 9 won.
Write a program that prints the expected cost of removing the bricks.