Firewall

Interview

Time limit1sMemory limit1024 MB

Summary

Simulate a rule list where each packet is checked top to bottom against port, IP, and a rate limit over the last 1000 packets, printing the action for every matching rule until accept or drop.

Level: Medium5 of 10
Topics: Simulation, Implementation, Queue, Array
Solved: No attempts yet

Problem

On the Internet, there are many bad guys who always try to hack other people's computers. 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 traffic based on different criteria, to shut out unauthorized access. In this problem, we are going to code the part of the firewall that determines whether 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.

Examples3

Example 1

Input

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

Expected output

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

Example 2

Input

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

Expected output

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

Example 3

Input

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

Expected output

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