가희와 지하철역 저장 시스템 2

가희는 멍멍철도공사에서 관리하는 n개의 지하철역 정보를 보기 위해, 지하철역 관리 시스템을 운영하고 있습니다. 이 시스템에서, n1번 노드에서 n2번 노드로 데이터를 보내는 전송 시간은 아래와 같이 계산됩니다.

• 데이터가 여러 회선을 통해 전송된 경우, 경로상에 있는 회선들의 전송 시간을 모두 더한 값이 됩니다.
• n1번 노드에서 n2번 노드로 데이터를 보내는 전송 시간은 n1번 노드에서 노드 n2번 노드로 가는 경로 중 총 전송 시간이 가장 작은 값이 됩니다.

[그림 1]은 4개의 노드로 이루어진 시스템을 나타냅니다.

[그림 1] 노드 4개로 이루어진 시스템

[그림 1]에서 4번 노드에서 1번 노드로 데이터를 보내는 전송 시간은 4입니다. 4번 노드에서 1번 노드로 갈 때, 4번 노드와 3번 노드를 연결하는 회선, 3번 노드와 2번 노드를 연결하는 회선, 2번 노드와 1번 노드를 연결하는 회선의 전송 시간을 모두 더한 값이 4이기 때문입니다. [그림 2]는 [그림 1]의 시스템에서 4번 노드와 2번 노드를 연결하는 회선이 하나 추가된 것입니다.

[그림 2] 그림 1에서 연결 관계가 하나 추가된 시스템

[그림 2]에서 4번 노드에서 1번 노드로 데이터를 보내는 전송 시간은 2입니다. 4번 노드에서 2번 노드를 연결하는 회선, 2번 노드에서 1번 노드를 연결하는 회선을 거치는 것이 총 전송 시간이 가장 적기 때문입니다.

지하철역 저장 시스템은 아래와 같이 동작합니다.

• n개의 지하철역에 대한 정보는 하나의 bucket 노드에 저장되어 있습니다.

• 지하철역 s의 정보를 출력해 달라는 요청이 요청 노드 r에서 들어온 경우

  • r에서 전송 시간이 가장 적은 cache 노드를 찾습니다. 그러한 노드가 여러 개라면, id가 가장 작은 cache 노드를 찾습니다.

  • 만약, 해당 cache 노드에 지하철역 s에 대한 정보가 있다면, cache 노드로부터 정보를 얻어와서 출력합니다.

  • 그렇지 않으면,

    • cache 노드 c가 bucket 노드에서 지하철역 s에 대한 정보를 얻어옵니다.
    • cache 노드 c에 지하철역 s에 대한 정보를 저장합니다.

지하철역 s에 대한 정보에 접근했다는 것은 둘 중 하나를 수행했다는 것을 의미합니다.

• cache 노드 c에 지하철역 s에 대한 정보가 있어서, 해당 노드로부터 s에 대한 정보를 얻어왔습니다.

• cache 노드 c에 지하철역 s에 대한 정보가 없어서

  • bucket 노드에서 지하철역 s에 대한 정보를 얻어옵니다.
  • 이 정보를 cache 노드 c에 저장합니다.

h개의 역을 저장할 수 있는 각각의 cache 노드는 더 이상 지하철역 s에 대한 정보를 저장할 수 없을 때, 아래와 같이 동작합니다.

• cache 노드 c가 지하철역 s에 대한 정보를 저장할 수 없다면, 가장 오랫동안 접근하지 않은 지하철역 정보를 제거합니다.
• cache 노드 c에 지하철역 s에 대한 정보를 저장합니다.

예를 들어 지하철역 3개의 정보를 저장할 수 있는 cache 노드 c1이 있다고 해 보겠습니다. 그리고 요청이 아래 [표 1]과 같이 들어왔다고 해 보겠습니다.

[표 1] cache 노드 c1에 들어온 요청

시각 4에, LINE역에 대한 요청을 수행하면 cache 노드 c1에는 OSAKA, LOOP, LINE역에 대한 정보가 저장되게 됩니다. 다음 시각 5에 NOZOMI역에 대한 요청을 수행할 때

• 지하철역 NOZOMI에 대한 정보가 cache 노드 c1에 없습니다.

• 따라서, bucket 노드로부터 NOZOMI역에 대한 정보를 얻어온 후, cache 노드 c1에 저장합니다. 그런데

  • 이미 c1에는 지하철역 3개의 정보가 저장되어 있습니다.
  • 따라서, 가장 오랫동안 요청이 들어오지 않은 OSAKA역에 대한 정보를 cache 노드 c1에서 제거합니다.

요청 노드 r번 노드에서 지하철역 s에 대한 정보를 출력해 달라는 요청이 수행되는 시간은 아래와 같이 구할 수 있습니다.

• r번 노드에서 전송 시간이 가장 적은 cache 노드를 찾습니다. 만약에 그러한 것이 여러 개라면, id가 가장 작은 cache 노드를 찾습니다. 이 노드를 c1번 노드라 할 때

  • c1번 노드에 지하철역 s에 대한 정보가 있는 경우 2×(r번 노드에서 c1번 노드로 데이터를 보내는 전송 시간)
  • 그렇지 않은 경우 2×(r번 노드에서 c1번 노드로 데이터를 보내는 전송 시간 + c1번 노드에서 bucket 노드로 데이터를 보내는 전송 시간)

지하철역에 대한 정보를 출력해 달라는 요청이 Q번 주어졌을 때, 각각의 요청이 수행되는 시간을 구해주세요.

첫 번째 줄에 지하철역의 개수 n과 노드의 개수 m, 문제에서 설명한 h와 Q가 공백으로 구분되어 주어집니다.

다음 n개의 줄에는 한 줄에 하나씩 지하철역 이름이 주어집니다.

다음 m개의 줄에는 노드에 대한 정보가 아래 포맷으로 주어집니다.

{node_id} {node_type}

이때 node_id는 1 이상 109 이하의 정수로 주어지며, node_type은 3개 중 하나로 주어집니다.

• R
  • 요청 노드를 의미합니다.
• C
  • cache 노드를 의미합니다.
• B
  • bucket 노드를 의미합니다.

다음 줄에 노드와 노드의 연결 관계 수 k가 주어집니다.

다음 k개의 줄에 아래와 같은 포맷으로 노드와 노드를 연결하는 회선 정보가 주어집니다.

{node1} {node2} {rt}

이는 node1와 node2를 연결하는 회선이 있고, 이 회선의 전송 시간이 rt임을 의미합니다.

다음 Q개의 줄에 요청에 대한 정보가 아래와 같은 포맷으로 주어집니다.

{node1} {station_name}

이는 id가 node1인 노드에서 역 이름이 station_name인 역에 대한 정보를 출력해 달라는 요청을 했음을 의미합니다. 이때, station_name은 멍멍철도공사에서 관리하는 역 중 하나로 주어집니다.

요청 하나가 들어올 때마다 각각의 요청이 처리되는 시간을 한 줄에 하나씩 출력해 주세요.

• 1 ≤ n ≤ 2×105
• 1 ≤ m ≤ 300
• 1 ≤ h ≤ n
• 1 ≤ Q ≤ 2×105
• 1 ≤ k ≤ mC2
• 1 ≤ rt ≤ 300
• 역 이름은 길이가 1 이상 10 이하이며, 대소문자와 숫자로만 이루어져 있습니다.
• 멍멍철도공사에서 관리하는 n개의 역 이름이 중복되는 경우는 없습니다.
• 역에 대한 정보를 출력하라는 요청은 cache 노드나 bucket 노드에서 이루어지지 않습니다.
• bucket 노드는 하나만 있으며, cache 노드는 최소 하나 이상 있습니다.
• 서로 다른 노드 번호를 가진 임의의 두 노드를 직접 연결하는 회선은 0개 또는 1개입니다.
• bucket 노드로부터 bucket 노드가 아닌 다른 임의의 노드로 1개 이상의 회선을 거치면 갈 수 있습니다.