OpenKattis
Onlinekvalet 2016

#### Start

2015-12-02 20:15 CET

## Onlinekvalet 2016

#### End

2015-12-06 22:15 CET
The end is near!
Contest is over.
Not yet started.
Contest is starting in -2667 days 2:40:52

98:00:00

0:00:00

# Problem BBrandvägg

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.

## Input

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$.

## Output

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.

## Scoring

Your solution will be tested on a number of test case groups. To get points for a group you have to solve all the test cases in that group.

 Group Points Limits 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$
Sample Input 1 Sample Output 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

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

Sample Input 2 Sample Output 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

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

Sample Input 3 Sample Output 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

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