볼리비아 요리 레스토랑에서는 1부터 N까지 번호가 붙여진 N명의 셰프가 일하고 있습니다. 셰프 i (1 ≦ i ≦ N)는 맛이 A_i인 실판초와 맛이 B_i인 피케마초를 만들 수 있습니다.

하지만 셰프들은 고집이 세서 사이가 안 좋은 2인 조합이 M개 있습니다. 사이가 안 좋은 2인 조합의 j번째 (1 ≦ j ≦ M)는 셰프 U_j와 셰프 V_j의 2인 조합입니다.

이 레스토랑에 오는 손님은 다음과 같이 요리를 먹습니다.

1 ≦ p < q ≦ N을 만족하는 정수 p, q를 선택하고, 셰프 p와 셰프 q의 2인 조합에 요리를 만들도록 의뢰합니다. 단, 사이가 안 좋은 2인 조합에 요리를 의뢰할 수는 없습니다. 실판초와 피케마초 각각의 요리는 셰프 p와 셰프 q 중 맛이 더 높은 셰프가 만듭니다. 만약 두 셰프가 같은 맛의 요리를 만들 수 있다면, 둘 중 하나가 만듭니다. 한 명의 셰프가 두 가지 요리를 모두 만들 수 있다는 점에 유의하십시오. 손님의 만족도는 실판초의 맛과 피케마초의 맛 합계입니다. 이 레스토랑에는 1부터 Q까지 번호가 붙여진 Q명의 손님이 방문합니다.

손님 k (1 ≦ k ≦ Q)는 요리를 만들 수 있는 2인 조합 중, 만족도가 X_k번째로 높은 2인 조합에 요리를 의뢰하고자 합니다. 구체적으로 만족도를 S로 정의하며, S × N^2 + p × N + q가 X_k번째로 높은 셰프 p와 셰프 q (1 ≦ p < q ≦ N)의 2인 조합에 요리를 의뢰합니다.

레스토랑의 셰프와 손님의 정보가 주어졌을 때, 손님 k (1 ≦ k ≦ Q)의 만족도를 구하는 프로그램을 작성하세요.

#8231 upload 68 done 7 how_to_reg 7 call_split Subtask

볼리비아 셰프 timer 3s memory 1024MB

#8231
Subtask

볼리비아 셰프 3s 1024MB