시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 1024 MB 3 1 1 33.333%

문제

On the Internet, there are many bad guys who always try to hack the computers of others. They steal cat pictures, bank logins and membership lists on programming dating sites. One of the first countermeasures against network-based attacks is the firewall. A firewall filters some network trafik based on different criteria, to shut out unauthorized access. In this problem, we are going to code the part of the firewall that determines of a certain message sent to a server over a network should be dropped or accepted.

A firewall consists of a number of rules in a long list. A rule is on the form "if [list of conditions] are true, perform an action". These conditions are one of

  • port=XYZ - if the message was sent to port XYZ.
  • ip=XYZ - if the message was sent from the IP-address XYZ.
  • limit=XYZ - if at least XYZ of the last 1000 messages (including the one just received) was sent from this IP-address.

and the actions are one of

  • accept - let the package through the firewall. Print accept packet-ID.
  • log - print log packet-ID.
  • drop - block the packet. Print drop packet-ID.

Some examples of rules with explanations:

  • accept - always accept the packet.
  • accept ip=127.0.0.1 - accept the packet if it comes from the IP-address 127.0.0.1.
  • drop port=22 ip=192.168.1.1 - drop the packet if its from the IP-address 192.168.1.1 and sent to port 22.
  • log port=80 limit=500 - log the packet if it was sent to port 80, and at least half of the last 1000 messenges was sent from this IP-address.

When a packet enters the firewall, it looks at every rule in the list, top to bottom, until it reaches a rule that matches the packet. The given firewall will always be constructed such that a packet will be accepted or dropped before the end of the list.

입력

The first line of input contains an integer $1 \le N \le 100$, the number of rules in the firewall.

The next $N$ lines contains the rules in the list, one rule on each line.

The next row contains an integer $P \le 10\,000$, the number of packets arriving to the firewall. They are given in the order of arrival. A packet is on the form IP:port, for example 127.0.0.1:123. The packet ID is just the position of the packet in this list. The first packet has id $1$ and the last ID $P$.

A port is an integer $1 \le p \le 65535$.

출력

For each packet, you are to run it through the firewall until it is accepted or dropped. Each action that is taken describes what to print. Note that since the action log doesn't stop the packet in the firewall, each packet could result in multiple lines of output.

서브태스크

번호 배점 제한
1 7

$P \le 10\,000$. There are only accept actions.

2 15

$P \le 10\,000$. No rule has a condition.

3 29

$P \le 10\,000$. There are no limit conditions.

4 25

$P \le 100$

5 14

$P \le 1\,000$

6 10

$P \le 10\,000$

예제 입력 1

6
accept ip=127.0.0.1
drop port=22
accept limit=5
accept port=80
accept port=10 port=11
drop
16
127.0.0.1:80
127.0.0.1:22
192.168.0.1:80
192.168.0.1:11
192.168.0.1:12
192.168.0.1:13
192.168.0.1:14
192.168.0.1:15
192.168.0.1:16
192.168.0.1:22
192.168.0.1:80
154.135.0.5:22
154.135.0.5:80
127.0.0.1:8080
215.215.5.8:5919
215.215.5.9:5919

예제 출력 1

accept 1
accept 2
accept 3
drop 4
drop 5
drop 6
accept 7
accept 8
accept 9
drop 10
accept 11
drop 12
accept 13
accept 14
drop 15
drop 16

예제 입력 2

4
accept ip=192.168.0.1
log port=22
accept
drop
16
127.0.0.1:80
127.0.0.1:22
192.168.0.1:80
192.168.0.1:11
192.168.0.1:12
192.168.0.1:13
192.168.0.1:14
192.168.0.1:15
192.168.0.1:16
192.168.0.1:22
192.168.0.1:80
154.135.0.5:22
154.135.0.5:80
127.0.0.1:8080
215.215.5.8:5919
215.215.5.9:5919

예제 출력 2

accept 1
log 2
accept 2
accept 3
accept 4
accept 5
accept 6
accept 7
accept 8
accept 9
accept 10
accept 11
log 12
accept 12
accept 13
accept 14
accept 15
accept 16

예제 입력 3

5
log limit=1
log limit=2
log limit=3
drop limit=1
accept
16
127.0.0.1:80
127.0.0.1:22
192.168.0.1:80
192.168.0.1:11
192.168.0.1:12
192.168.0.1:13
192.168.0.1:14
192.168.0.1:15
192.168.0.1:16
192.168.0.1:22
192.168.0.1:80
154.135.0.5:22
154.135.0.5:80
127.0.0.1:8080
215.215.5.8:5919
215.215.5.9:5919

예제 출력 3

log 1
drop 1
log 2
log 2
drop 2
log 3
drop 3
log 4
log 4
drop 4
log 5
log 5
log 5
drop 5
log 6
log 6
log 6
drop 6
log 7
log 7
log 7
drop 7
log 8
log 8
log 8
drop 8
log 9
log 9
log 9
drop 9
log 10
log 10
log 10
drop 10
log 11
log 11
log 11
drop 11
log 12
drop 12
log 13
log 13
drop 13
log 14
log 14
log 14
drop 14
log 15
drop 15
log 16
drop 16

출처

Olympiad > Swedish Olympiad in Informatics > 2016 > Online Qualification B번

  • 문제를 만든 사람: Johan Sannemo

채점 및 기타 정보

  • 예제는 채점하지 않는다.