스택 자료구조를 활용해 해결하는 4가지 심화 명령어들을 일괄 처리하는 종합 시뮬레이터를 작성하십시오.

명령어 종류 및 규격:
1. EXPR expression: 수식 유효성을 검사하여 타당하면 정수 몫 연산 결과를, 비유효 시 INVALID를 출력합니다.
2. MATRIX n m val_11 ... val_nm: $n \times m$의 0-1 행렬 속에서 1로 구성된 최대 직사각형 넓이를 출력합니다.
3. PLANET n a_1 ... a_n: $n$개 행성의 방향 및 질량을 입력받아 충돌 시뮬레이션을 수행하고, 최종 생존 목록을 공백 구분 출력합니다.
4. LRU k n req_1 ... req_n: 용량 $k$인 LRU 캐시의 HIT/MISS 결과들을 한 줄에 공백 구분 출력하고, 최종 캐시 상태(MRU→LRU)를 그 뒤에 공백 나열하여 출력합니다.

[제약 조건]
• 명령 수 $N$: $1 \le N \le 10$ (정수)
• PLANET: 행성 수 $n \le 100{,}000$, LRU: 요청 수 $n \le 10{,}000$

첫째 줄에 실행할 명령어의 개수 $N$이 주어집니다. ($1 \le N \le 10$)
둘째 줄부터 $N$개의 줄에 걸쳐 각 줄에 위의 명령어 규격이 하나씩 주어집니다.

각 줄의 명령을 수행한 결과를 순서대로 한 줄에 하나씩 출력합니다.
(단, LRU 명령은 HIT MISS HIT 3 2 1과 같이 결과 목록과 최종 상태를 연이어 한 줄에 표시해야 함)

4
EXPR (3+4)*5
MATRIX 4 4 0 1 1 0 0 1 1 1 1 1 1 1 1 1 0 0
PLANET 3 5 10 -5
LRU 3 6 1 2 3 1 4 5

35
6
5 10
MISS MISS MISS HIT MISS MISS 5 4 1